Why can't we exploite finiteness to prove incompleteness in NP?

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.

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.

StackExchange Computer Science Q#63726, answer score: 8