Are there complexity classes with provably no complete problems?

Question

A problem is said to be complete for a complexity class $\mathcal{C}$ if a) it is in $\mathcal{C}$ and b) every problem in $\mathcal{C}$ is log-space reducible to it. There are natural examples of NP-complete problems (SAT), P-complete problems (circuit-value), NL-complete problems (reachability), and so on.

Papadimitrou states that "semantic" complexity classes like (I think) BPP are less likely to admit complete problems. Then again, we do not actually know whether P = BPP or not, and if so, there would be BPP-complete problems. (There exist IP-complete problems, since IP=PSPACE, and determining whether a quantified boolean formula is satisfiable is PSPACE-complete.)

Question: Are there any natural complexity classes that can be shown not to have complete problems?

I think this question has to be modified slightly, because I would imagine $Time(n)$ has no complete problems because log-space reductions can introduce a polynomial factor. So, in the word "natural," I include the assumption that the complexity class should be invariant under polynomial transformations (I don't know how to make this precise, but hopefully it is clear).

(Also, time or space bounds should be at least $\log n$, of course.)

Edit: A commenter has pointed me to an interesting result of Sipser that $\mathrm{BPP}^M$ for $M$ a suitable oracle does not have complete problems. Is the same true for a (less fancy) class of the form $\bigcup_f TIME(f)$, where the union is over a class of recursive functions $f$ that are all polynomially related to each other? (Same for $\bigcup_f NTIME(f)$, and ditto for space.

Have you looked at Sipser's results (mentioned also in http://en.wikipedia.org/wiki/Complete_%28complexity%29 ) — Gjergji Zaimi, Jun 09 '10 at 11:08
Also in this article the author says that POLYLOGSPACE doesn't have complete problems http://www2.research.att.com/~dsj/columns/col7.pdf and gives a reference to R. V. Book, "Translational lemmas, polynomial time, and $(logn)^j$-space". — Gjergji Zaimi, Jun 09 '10 at 12:04
@Gjergji: Fair enough - I think that's because Space(log n) is strictly contained in Space(log^2 n), and so on, by the hierarchy theorem, and a complete problem in POLYLOGSPACE would imply that this hierarchy would collapse to some finite level. (The same should be true for time because of the time hierarchy theorem.) But log(n) and log^2(n) are not polynomially related in the input n (which is what I had meant). — Akhil Mathew, Jun 09 '10 at 12:48
Akhil, your profile says that you are a senior in high school. In this case, I am extremely expressed by your high level of mathematical sophistication! — Joel David Hamkins, Jun 09 '10 at 12:54

score 17 · Answer 1 · answered Jun 09 '10 at 15:51

17

Here's a really simple class that is very natural and has no complete problems: ALL, the class of all languages. The reason is that there are uncountably many problems in ALL, but only countably many Turing machines to go around (for reductions), so every problem in ALL cannot be reduced to a single problem in ALL.

Similarly, any class with advice, like P/poly, L/poly, BQP/qpoly, or even P/1 does not have complete problems (using the same argument).

answered Jun 09 '10 at 15:51

Rune

2,386

13

Also, the class NONE = ∅. It contains no language, so in particular it has no complete language. :-) – Antonio E. Porreca Jun 09 '10 at 18:52

score 16 · Answer 2 · answered Jun 09 '10 at 19:39

16

Another class without complete problems w.r.t. logspace or polytime reductions (not an union of classes TIME(f) for some family of polynomially related functions f, but still relatively natural in my opinion) is

ELEMENTARY = TIME(2ⁿ) ∪ TIME(2^2ⁿ) ∪ TIME(2^{2^2ⁿ}) ∪ TIME(2^{2^{2^2ⁿ}}) ∪ ⋯

If L were ELEMENTARY-complete, then it would belong to some level of this hierarchy, and all problems above could be reduced to it. But this hierarchy is known to be proper (time hierarchy theorem), contradiction.

answered Jun 09 '10 at 19:39

Antonio E. Porreca

1,155

1

Moreover, the same argument applies to the polynomial hierarchy if it does not collapse (though this is unknown and does not follow from the hierarchy theorem). – Akhil Mathew Jun 09 '10 at 19:52
3

The same argument works for any hierarchy that is known to be infinite. I guess this general method captures most of the examples given in this thread till now, like POLYLOGSPACE, ELEMENTARY, etc. – Rune Jun 09 '10 at 20:03
Oh, I somehow missed the comments mentioning POLYLOGSPACE; indeed, it’s the same argument. – Antonio E. Porreca Jun 09 '10 at 20:08

score 13 · Accepted Answer · answered Jun 09 '10 at 12:27

The zoo of complexity classes extends naturally into the realm of computability theory and beyond, to descriptive set theory, and in these higher realms there are numerous natural classes which have no members that are complete, even with respect to far more generous notions of reduction than the one you mention.

For example, consider the class Dec of all decidable sets of natural numbers. There can be no decidable set $U$ such that every other decidable set $A$ reduces to it in time uniformly bounded by any computable function $f$ (even iterated exponentials, or the Ackerman function, etc.). In particular, it has no member that is complete in your sense. If there were such a member, then we would be able to consruct a computable enumeration $A_0$, $A_1$, $\ldots$ containing all decidable sets, which is impossible since then we could diagonalize against it: the set of $n$ such that $n\notin A_n$ would be computable, but it can't be on the list.
The class of all arithmetically definable sets is obtained by closing the decidable sets (or much less) under projection from $\mathbb{N}^{n+1}\to \mathbb{N}^n$ and under Boolean combinations. The members of this class are exactly the sets that are defined by a first order formula over the structure $\langle\mathbb{N},+,\cdot,\lt\rangle$, and the hierarchy is stratified by the complexity of these definitions. This class has no member that is complete with respect to any computable reduction, and even with respect to any arithmetically definable reduction of bounded complexity, for in this case the hierarchy would collapse to some level $\Sigma_n$, which is known not to occur.
A similar argument works for the hyperarithmetic hiearchy, which can have no universal member hyperarithmetic reductions of any fixed complexity.
And similarly for the projective hiearchy on sets of reals.

The general phenomenon is that there are numerous hierarchies growing from computability theory into descriptive set theory which are all known to exhibit strictly proper growth in such a way that prevents them from having universal members.

Thanks!
How do semidecidable sets fit into this hierarchy? If I'm not mistaken, there is a "universal" semidecidable set from the universal Turing machine, but presumably it cannot belong to the arithmetic hierarchy then, right? — Akhil Mathew, Jun 09 '10 at 12:51
There is a universal c.e. set, and all other c.e. sets reduce to it in linear time. Every c.e. set is arithmetic, at the level of $\Sigma_1$, and in fact this characterizes the c.e. sets. But this set is not universal for all arithmetic sets, only for the bottom level $\Sigma_1$. Similarly, there is a universal $\Sigma_n$ set for any fixed $n$, and this is how one can see the arithmetic hierarchy does not collapse. — Joel David Hamkins, Jun 09 '10 at 12:59

score 4 · Answer 4 · answered Jun 14 '10 at 03:25

This is more of a comment than an answer, but the comment go too long. From this thread, there seem to be two different themes to coming up with classes without complete problems.

Completeness is defined using two properties. L is X-complete if
(1) L is in X
(2) L is X-hard (under some suitable notion of efficient reductions)

The first theme involves classes which have hard problems, but if the hard problem were a member of the class itself, it would cause problems. The examples of POLYLOGSPACE and ELEMENTARY fall in this category. Both have hard problem, of course, but if the hard problem were a member of the class, some hierarchy theorem would be violated. (Space hierarchy and time hierarchy theorems, respectively.) Similarly one could come up with more examples of this kind.

The second theme involves classes which have no hard problems, such as ALL or P/poly. These classes don't have a complete problem for a fundamentally different reason than the previous case.

It would be interesting to see if there are other classes which fail to have complete problems for completely different reasons.

score 0 · Answer 5 · edited Apr 12 '17 at 21:34

I'm not sure that it's entirely correct, but here goes. Let $f(n)$ be a proper complexity function (a.k.a. space and time constructible, etc.) and consider the class $\mathcal{C} = \bigcup_{P,Q} \mathsf{DTIME} (Q(f(P(n))))$, where $P,Q$ ranges over polynomials with natural number coefficients. Suppose $f(n) \geq n$. Then the language $L=(M,x,P,Q)$: $M$ is a deterministic Turing machine that accepts string $x$ in at most $Q(f(P(n))$ steps should be $\mathcal{C}$-complete. Indeed, verification is just a mechanical process of simulating the Turing machine (which can be done in polynomial time on the length of $M$ and $x$), and every language decided by a Turing machine $M$ in $\mathsf{DTIME}(Q(f(P(n)))$ should reduce to $L$ based on the machine $M$. The same should hold for nondeterministic complexity classes.

I've seen something like this for $\mathsf{NP}$ (this is how the Cook–Levin theorem is proved, if I understand correctly), and I think it should generalize, and that natural complexity classes based solely on a time constraint (which is sufficiently large) should admit complete problems.

Are there complexity classes with provably no complete problems?

5 Answers5