This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science
There's no such thing as the class of all problems without qualification, hence no such thing as the class of nonelementary problems (since its union with the class of elementary problems would be the class of all problems). It's fine to say that a problem is nonelementary, meaning that it is a problem that is not in the class of elementary problems, but those problems don't form a class other than within some specified larger class. This article does not specify the containing class whence the concept is undefined. Vaughan Pratt (talk) 19:56, 29 July 2014 (UTC)[reply]
One can for instance define an alphabet to be a prefix of the natural numbers, a string to be a finite sequence of natural numbers, a language to be an alphabet and a set of strings that are all restricted to that alphabet, and a problem to be an input alphabet, an output alphabet, and a function from strings over the input alphabet to strings over the output alphabet. In this formalism the set of all problems is perfectly well defined and not even a proper class. So why do you say there is no such thing? The only thing that could cause foundational problems would be to allow "any finite set" (whatever that means) to act as an alphabet, but that's a silly quibble — they're all isomorphic to prefixes of the naturals. Or maybe you'd like your alphabets to be any hereditarily finite set? That should work too. —David Eppstein (talk) 05:14, 9 October 2014 (UTC)[reply]
Two points, David. First, my concern was not about proper classes but about whether an arbitrary string over a given alphabet (of whatever cardinality, two, 26, or hereditarily finite) defined a class. Logicians customarily use the term "well formed formula" for this purpose, but "well formed" is not an absolute concept in the same way the set of natural numbers is.
Second, your citation contains only the concept NONELEMENTARY(f(n)) parametrized by a function f of n, which is a fine notion. In order to properly source an article titled NONELEMENTARY you need to produce a source containing the unparametrized version. If you do then I'll accept that, but I'll also ask its author(s) what they mean by the concept, since its meaning is less clear to me than it seems to be to you. Vaughan Pratt (talk) 05:29, 9 October 2014 (UTC)[reply]
Meanwhile the article is in an inconsistent state because Wikipedia bounced my edits making it consistent because of the edit conflict created by your Vorobyov source. What to do? I saved the edits and so can easily restore them, but I'd like to reach some sort of consensus first. Vaughan Pratt (talk) 05:43, 9 October 2014 (UTC)[reply]
Well, I still don't understand what you mean. "whether an arbitrary string over a given alphabet (of whatever cardinality, two, 26, or hereditarily finite) defined a class"? Do you mean set of sets of strings here? Or do you really mean a single string? Because I don't see why a class should have to be describable or definable any more than a real number should have to be. Some real numbers are described by strings such as $\sqrt\pi$. Some are not. Does that mean that there is no such thing as the class of all real numbers without qualification? Or if that's not what you mean then what do you mean? In what sense is the class of all problems not a complexity class, or not a mathematical object, or otherwise nonsensical to talk about? —David Eppstein (talk) 06:57, 9 October 2014 (UTC)[reply]
Sorry, I was being overly constructive. Assuming a binary input alphabet and recognition problems, I'm fine with defining the set of all strings as 2*, the set of all languages (aka recognition problems) as 2^2*, and the set of all families of languages (aka the class of all recognition problems) as 2^2^2*. While nonconstructive (no more or less than the set of all reals as you point out) this at least supplies a set-theoretic definition of the class of all problems, suitably understood.
But is Vorobyov an adequate source for this definition? He defines NONELEMENTARY(f(n)), but where does he define NONELEMENTARY? Is Wikipedia the first place where this class appeared? Vaughan Pratt (talk) 07:24, 10 October 2014 (UTC)[reply]
As an explicit class? Maybe, I'm not sure. I wasn't able to find better references than that, partly because the keywords are a little too broad for searching easily. Certainly there has been past work on individual problems with nonelementary complexity, already cited here. It's not in the complexity zoo. So maybe focusing the article more on problems (as you have already started with the move to a new title) and less on classes would be a good idea. —David Eppstein (talk) 07:35, 10 October 2014 (UTC)[reply]
