6
$\begingroup$

It is well established that the class of recursive languages is strictly contained in the class of recursively enumerable languages (Rec $\ne$ RE). Any finite language is decidable and hence can not be RE-complete. My intuition is that an RE-complete language contains infinite number of (finite) strings (information) and can not be reduced to a finite language.

The situation is different for the class NP since we can not rule-out finite NP-complete languages. If P=NP then there is some finite NP-complete language (under Karp reduction).

Is there an intuition (or evidence) that explains why finite languages can not be complete for NP?

I am looking for an intuition (evidence) that supports the conjecture that all NP-complete languages must be infinite (It should not assume anything about P vs NP). Different notions of completeness inside NP may have significant impact on the properties of complete languages inside NP.

This was moved from a comment. Finiteness of complete languages shifts the focus on using the right notion of reduction to define completeness inside NP. The following post on CS Theory shows that defining completeness using injective Karp reductions would prove $P \ne NP$. The reason is that SAT is infinite language and can not be reduced to a finite language using injective Karp reductions.

$\endgroup$
  • $\begingroup$ Your edit doesn't change anything. As the answer explains, there are finite NP-complete languages if and only if P = NP. Hence, you are asking for an intuition for a statement that may not be true -- that's dangerous. How can you hope to get useful answers? If there were any, we'd probably have solved the P=?NP question already. $\endgroup$ – Raphael Sep 21 '16 at 21:37
  • $\begingroup$ You should edit to clarify that. Currently, your question talks only about "completeness" which defaults to "complete wrt Karp-reductions" in the absence of other statements. $\endgroup$ – Raphael Sep 21 '16 at 22:04
  • $\begingroup$ You added a tautology, but no clarity to the question. $\endgroup$ – Raphael Sep 22 '16 at 6:51
  • $\begingroup$ I'm not sure I understand, but it seems to me that you're stretching more out of "If P=NP then there is a finite NP-complete language" than this statement deserves. If P=NP then the language {1} is NP-complete since one can in polynomial time map any string in the NP language to 1 and any string not in it to something else. So you seem to be focusing on the property of finiteness but to me all the difficulty is wrapped up in the existence of the polynomial-time reduction and the focus on finiteness doesn't help anything. $\endgroup$ – usul Sep 22 '16 at 19:34
  • 1
    $\begingroup$ Please don't use "edit:..."; see meta.cs.stackexchange.com/q/657/755. $\endgroup$ – D.W. Sep 24 '16 at 16:23
8
$\begingroup$

Here is a good reason why finiteness does not help: Let $P_{inf}$ and $NP_{inf}$ be the sets of infinite languages in $P$ and $NP$. Then we may focus on proving $P_{inf}\not=NP_{inf}$, rather than $P\not=NP$. But $P_{inf}=NP_{inf}$ if and only if $P=NP$!

The question as I understand it is, why can't we exploit the fact that these languages are finite in a proof of $P\not=NP$, like we did when we proved $R\not=RE$? But the premise is wrong: the proof that $R\not=RE$, that the Halting Problem is undecidable, does not reference the fact that there are finite languages in $R$. Of course it makes intuitive sense that, since $R$ contains finite languages, it cannot contain $RE$, but in fact $R\not=RE$ follows from the fact that Turing Machines cannot be analysed by other Turing Machines, and, in my view, the fact about finite languages is a quirk which follows from the definitions, as we may as well have considered $R_{inf}\not=RE_{inf}$.

If $R\not=RE$ comes from the fact that undecidability cannot be eliminated, then $P\not=NP$, if true, comes from the fact that nondeterminism cannot be efficiently eliminated.

I should clear up some technicalities. If a language contains a finite amount of strings, it can be decided in constant time, $O(1)$, so it is definitely in P, as you note. If P=NP, then every language in P is also NP-Complete (the reduction is simple: given a string, solve it in polynomial time, and then print a fixed yes/no instance of the other problem). So not only is there some finite NP-Complete language, all nontrivial* finite languages are NP-Complete if P=NP. On the other hand, if $P\not=NP$, then no finite language is NP-Complete. Your intuition about RE-Complete languages containing infinite strings is wrong: those languages contain an infinite number of finite strings.

*A nontrivial language is one with both yes- and no-instances. The two trivial languages are the empty language $\emptyset$ and the full language $\Sigma^{*}$, which have no yes- and no no-instances, respectively, which is why no other language can many-one reduce to them.

$\endgroup$
  • 4
    $\begingroup$ "So not only is there some finite NP-Complete language, all finite non-trivial languages are NP-Complete if P=NP" $\endgroup$ – xavierm02 Sep 21 '16 at 19:02
  • $\begingroup$ This is the point that motivated my post: If some language is RE-complete then it must be infinite. The same can not be said for NP-complete languages. Why?. So your understanding in your second paragraph is incorrect. $\endgroup$ – Mohammad Al-Turkistany Sep 21 '16 at 19:42
  • $\begingroup$ @MohammadAl-Turkistany The statement "$L$ is NP-Complete, therefore $L$ is infinite" is correct if P$\not=$NP and is not correct if P=NP. We have not proved that that can't happen. Have I understood your question? $\endgroup$ – Lieuwe Vinkhuijzen Sep 21 '16 at 19:45
  • $\begingroup$ P vs NP is an open question. I am looking for an intuition that supports the conjecture that all NP-complete sets must be infinite. $\endgroup$ – Mohammad Al-Turkistany Sep 21 '16 at 19:48
  • $\begingroup$ @MohammadAl-Turkistany I brought up P vs NP because it and your question are the same: each implies the other. Why can't nondeterminism be efficiently simulated? Because then there are finite NP-Complete languages! Imagine how silly! That's intuition for P vs NP. Why can't there be finite NP-Complete languages? Because then P=NP. Imagine how silly! That's intuition for infiniteness of NPC languages. I have interpreted your question as asking why R vs RE doesn't carry over to P vs NP, but perhaps that wasn't exactly what you were asking. $\endgroup$ – Lieuwe Vinkhuijzen Sep 21 '16 at 19:57

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.