7
$\begingroup$

$\text{ALL}$ is literally the class of ALL languages.

Are there $\text{ALL}$—complete problems? That is, are there problems for which a solution would allow one to solve any problem whatsoever? Such problems could reasonably be considered"the hardest problems, bar none".

One such problem seems to be: given a problem and an input size, output it's truth table.

$\endgroup$
1
  • $\begingroup$ there is a sense in which this is exactly the concept behind Turing completeness/ TM-complete languages... $\endgroup$
    – vzn
    Jul 3, 2016 at 4:57

1 Answer 1

8
$\begingroup$

You haven't specified your notion of reduction, so I will assume that you choose some countable class of functions $\cal F$ which can be used for reductions (any subset of the computable functions would work here). Let $\cal L$ be any class of languages over some fixed alphabet $\Sigma$, say $\Sigma = \{0,1\}$. A language $K$ is hard for $\cal L$ (with respect to $\cal F$) if for every $L \in \cal L$ there exists $f \in \cal F$ such that $x \in L$ iff $f(x) \in K$. If also $K \in \cal L$ then we say that $K$ is complete for $\cal L$.

I will now show that no language is hard for $\mathsf{ALL}$. Suppose that $K$ were $\mathsf{ALL}$-hard. Let $f_x : x \in \Sigma^*$ be an enumeration of the functions in $\cal F$ (such an enumeration exists since both $\Sigma^*$ and $\cal F$ are countable). Define a language $L$ by $$ L = \{x : f_x(x) \notin K \}. $$ Since $L \in \mathsf{ALL}$, there exists a function $f \in \cal F$ such that for all $x \in \Sigma^*$, $x \in L$ iff $f(x) \in K$. Since $f \in \cal F$, there exists $x \in \Sigma^*$ such that $f = f_x$. For this particular $x$, $x \in L$ iff $f_x(x) \in K$. However, by definition $x \in L$ iff $f_x(x) \notin K$.

$\endgroup$
6
  • $\begingroup$ Interesting cardinality argument. What about the problem I gave in the question (given a function description, return its truth table)? It seems that this problem (which is of course very undecidable) would allow any problem whatsoever to be solved (get the truth table from the oracle, then look up the problem). Can you explain where my argument goes wrong, other than the fact that (obviously) no such oracle exists? $\endgroup$
    – Demi
    Jul 3, 2016 at 2:28
  • $\begingroup$ It's your intuition that goes wrong. You can't input a "problem", since problems don't have finite descriptions in general. $\endgroup$ Jul 3, 2016 at 6:32
  • $\begingroup$ So basically even an all-powerful oracle (that could answer any question asked of it) is still inadequate to solve some problems, because there is no way to give the oracle the needed information? $\endgroup$
    – Demi
    Jul 3, 2016 at 8:21
  • 1
    $\begingroup$ There is no such thing as an all-powerful oracle, exactly for this reason. The proof of undecidability of the halting problem can be extended to show that given any oracle $O$, the problem of deciding whether a Turing machine with access to $O$ halts remains undecidable even given access to $O$. On the other hand, we can construct an oracle which can either "redirect" to $O$ or solve the halting problem for machine with access to $O$. This oracle is more powerful than $O$. $\endgroup$ Jul 3, 2016 at 8:23
  • $\begingroup$ Ah okay. So the the reason that all-powerful oracles do not exist, while $EXP/exp = ALL$, is because the advice can depend on an infinite amount of information about the problem? $\endgroup$
    – Demi
    Jul 3, 2016 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.