Talk:Nonelementary problem

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)

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)

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)

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)

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)

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)

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)

suggestion: Hydra from Paris and Kirby

should the hydra problem from Goodstein's theorem be included in the list? Scubatoad (talk) 02:42, 16 April 2025 (UTC)

Notation for extended Grzegorczyk hierarchy

The definition makes use of an iterated function application, like in the class definition box, not a power of the value like in the text before. The cited paper uses the same correct notation in text and definition (5). The Wikipedia article has a notational typo. My fix has been reverted, just stating it "was ok". Please help to fix this. Molzer (talk) 06:04, 12 May 2026 (UTC)

Oh, I see. I misunderstood your fix. In computational complexity (which is what this article is about), at least as applied to specific algorithms, there is a standard notational convention under which $f^{k}(n)$ and $f(n)^{k}$ mean the same thing: the $k$th power of the number $f(n)$. So for instance, one frequently sees time bounds like $O(n\log ^{2}n)$ meaning the square of the logarithm, not the iterated logarithm. The $f^{k}(n)$ version is a bit of an abuse of notation but used because it makes some formulas a little neater by avoiding the need to parenthesize the function argument. I thought you were merely reverting to the less rigorous but equivalent exponentiation notation.

But what you actually want here is functional iteration, not exponentiation. The convention for that (when a bare superscript on a function is taken to mean exponentiation) is to parenthesize the superscript: $f^{(k)}(n)$, sometimes with an explanation that this is what the notation means. I have edited the article to use the superscript-parenthesis notation. —David Eppstein (talk) 06:36, 12 May 2026 (UTC)

Sounds great. At first I thought about the same fix: (k), instead of k. After checking in the cited reference, I saw k is used there always before the argument, similarly as I've then proposed. The "fine-grained" referencing was meant to give that hint, admittedly not very pretty. Molzer (talk) 10:53, 12 May 2026 (UTC)