Talk:Negligible function

Merge

This should never have been split IMHO. See discussion at Talk:Negligible (English) --Nigelj 20:50, 14 December 2006 (UTC)

Sorry, I didn't check this item until just now. I created the "negligible (complexity theory)" item and did the "move". The word "negligible" is a very common term. It is likely that "negligible (in field A)" and "negligible (in field B)" are irrelevant to each other. They are connected to each other by sheer coincidence because of a commonly used term. Here "negligibility" is fundamental to some branches of complexity theory, such as cryptography. The meaning is very different from those used in other fields. I think that the better way to handle this issue would be like this:

1. Keep the "negligible (complexity theory)" record, and use <onlyinclude>contents</onlyinclude> tags in the record to identify the main contents.

2. Move "negligible (english)" back to "negligible", create a "Definition in complexity theory" section and use {{:negligible (complexity theory)}} to include the proper contents from the "negligible (complexity theory)" record.

This way, "negligible" is restored to the original state, and "negligible (complexity theory)" is also separated from other irrelevant "siblings". Hope this will serve everybody's needs.--Jiejunkong 00:17, 22 February 2007 (UTC)

There is a third option: make this a redirect to whatever article in complexity theory discusses these things. I was going to prod it as a dictionary definition before I read the talk page. CMummert · talk 14:18, 1 March 2007 (UTC)

IMHO, "negligible (complexity theory)" is irrelevant to the English dictionary definition. To me, it is similar to the case of "Turing Machine" (or some other examples), which cannot be deleted and merged into the term "Machine". This term is the foundation of some booming research areas. It worths an individual record.--Jiejunkong 22:44, 2 March 2007 (UTC)

The difference is that there is an entire article about Turing machines (because there is a lot to say about them) but I see no future with a long article on this topic. That's what I meant when I said this was a dictionary definition - it is an article that consists of a definition and nothing more. See WP:NOT#DICTIONARY. Unless someone can at least sketch an outline of how this could be fleshed out into a full article, it ought to be merged and/or deleted. CMummert · talk 22:50, 2 March 2007 (UTC)

Compared to the concept of "Turing Machine", this concept of "negligible" is much younger (thus presentable contents are likely shorter than "Turing Machine"'s). I think it is still too early to predict how important this concept is in the future, so instead I have added some descriptions about its past history. Hope these newly added contents differentiate the current record from a dictionary record. Another user has found an overlapping record "negligible function (cryptography)". IMO, the question is not about deleting the record, the question is about which name is the more proper one to use. For technical reasons, I think "negligible function (complexity theory)" is more proper, because (1) "negligible" has attracted some unnecessary arguments, which make "negligible function" a better name; (2) "negligible function" is in general used in all complexity theory related fields, not limited to provable security (foundations of cryptography).--Jiejunkong 00:51, 3 March 2007 (UTC)

I did a quick google search for negligible function and most hits seemed to be connected with cryptography so I thik that might be the better name to use, I've not found any sources which show that it is a widely used term in complexatity theory. Interesingly negligible function redirects to Colombeau algebra which seems to be a similar topic. --Salix alba (talk) 15:58, 3 March 2007 (UTC)

I think the "connection" googled out is about the "application" of this general concept to cryptography. But the concept itself is clearly more general than one of its major applications. Michael Sipser's book and Christos Papadimitriou's book are examples of complexity theory books, with formal cryptography treated as a branch of randomized complexity theory. Colombeau algebra looks like a relevant topic of randomized complexity theory. And generalized function is more general than all of the above. I didn't realize that "negligible function" is a viable option. Maybe a better way is to stop the redirection in the current "negligible function" record, and merge "negligible (complexity theory)", "negligible function (cryptography)", and applicable part of "Colombeau algebra" into this readily avaiable "negligible function" record.--Jiejunkong 23:20, 3 March 2007 (UTC)

I agree that this article and negligible function (cryptography) should be merged. They are talking about the same application of the concept (as far as I know, non-cryptographer complexity theorists don't talk about negligible functions, and the cryptographers that talk about negligible functions are complexity theorists). Furthermore, I don't understand why there is a definition at the top, and a huge, sometimes contradictory, definition (with too much background info) below. Blokhead 04:00, 15 June 2007 (UTC)

FYI, the definition at the top is basically from Silvio Micali's group. I don't understand why it is "contradictory". BTW, I support the merge of "negligible (complexity theory)" and "negligible function (cryptography)", also adding relevant part of "Colombeau algebra".--Jiejunkong 04:05, 15 June 2007 (UTC)

I just realized that you were saying that the "History" part is contradictory. Because some users wanted to merge the article into the English one (negligible (English)) and complained that the article is too short, I added this part to extend the length. It is based on my understanding of Colombeau's work.--Jiejunkong 05:04, 15 June 2007 (UTC)

I'd also support the merge between negligible function (cryptography) and negligible function (complexity theory). It's the same definition. Looking at the history part, I think we might consider to remove the claim negligible functions can be derived from continuous functions by replacing parts in the definitions. This definition X looks a little bit like definition Y math kind seems strange to me. 85.2.117.73 10:07, 12 August 2007 (UTC)

negligible function is definitely a better name. When we say something is negligible, we always mean that it is negligible with respect to an integer x. The definition here is no different from that used in cryptography. If there're no other places "negligible function" is defined differently, why don't we just use negligible function without the "(complexity theory)" or "(cryptography)"? --Eng2007 15:13, 5 August 2007 (UTC)

Agree to the view that negligible function without disambiguition suffix is a better name.--Jiejunkong 18:40, 12 August 2007 (UTC)

Ambiguous statements

It is important to state whether definitions are of the type "for all .. there exists .." or "there exists .. for all ..". However, many definitions are very unclear, for example this one:

(Negligible function) A continuous function $\mu (x):\mathbb {R} {\rightarrow }\mathbb {R}$ is negligible if for all sufficiently large $x$'s, for every positive polynomial $poly(x)={\frac {1}{\epsilon (x)}}>0$ such that

$|\mu (x)|<\epsilon (x)={\frac {1}{poly(x)}}.$

I think dropping the term "sufficiently large" and inserting explicit quantifiers makes the definitions more clear. 85.2.117.73 08:49, 12 August 2007 (UTC)

I guess what you mean is that the order, "for all positive polynomials", then "there exists an Nc", then "for all n larger than Nc", is critical to make the definition correct. English descriptions are normally ambiguious. Support your editings because pure math notions are better here.--Jiejunkong 18:46, 12 August 2007 (UTC)

About the continuity question 85.2.117.73 raised against the current content about "infinitesimal function"

In Algebras of generalized functions, Colombeau algebra is rated as the most widely used approach to construct associative differential algebras, where differentiable functions (at everywhere) must also be continuous (at everywhere). In the current content, I think "infinitesimal functions" should be renamed as "continuous infinitesimal functions" as infinitesimal functions could be non-continuous at certain points, but what are concerned here are "continuous infinitesimal functions". In other words, only continuous functions are studied in the algebraic system; Non-continuous functions are irrelevant here.--Jiejunkong 21:58, 13 August 2007 (UTC)

This terminology is not good at all

Because the function per se is not what is negligible.

What is negligible is the function's behavior as its argument approaches plus or minus infinity.

A much better terminology would be to call this kind of function "negligible at infinity".