# Poly time superset of NP complete language with infinitely many strings excluded from it

For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite?

A trivial version which does not stipulate the superset to have infinite complement has been asked at https://cs.stackexchange.com/q/50123/42961

For purposes of this question, you can assume that $P \ne NP$. As Vor explained, if $P = NP$ then the answer is "No". (If $P = NP$, then $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ is NP-complete. Clearly there is no superset of $X$ which is infinite and has an infinite complement, as the complement of $X$ has only a single element.) Thus we can focus on the case $P \ne NP$.

• If $P = NP$ then $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ is NP-complete. Clearly there is no superset of $X$ which is infinite and has an infinite complement (note that $\bar{X} = \{1\}$). So you can "focus" on what happens if $P \neq NP$. – Marzio De Biasi Dec 5 '15 at 20:32
• How about the relativized version: Is there an oracle $A$ s.t. all co-NP$^A$ sets are P$^A$-immune. – Lance Fortnow Dec 10 '15 at 13:41
• @LanceFortnow ...or for any complete language in a particular. Complexity class, is there always a non trivial superset of a lesser complexity. – ARi Dec 11 '15 at 5:01

Every $\mathsf{coNP}$-complete set contains an infinite subset in $\mathsf{P}$ assuming that

• pseudorandom generators exist, and
• secure one-way permutations exist.

In other words, assuming that these two conjectures are true, no $\mathsf{coNP}$-complete set is P-immune. As pointed out in the comments by Lance, this is implied by Theorem 4.4 of

(Kaveh has already shown that your question is equivalent to whether every $\mathsf{coNP}$-complete sets contains an infinite $\mathsf{P}$ subset. In other language, this is saying that no $\mathsf{coNP}$-complete set is "$\mathsf{P}$-immune." This is the language used in the above-referenced theorem.)

• ECCC draft – Kaveh Dec 9 '15 at 20:57
• By strong hard-core functions (and iteration), one-way permutations imply pseudorandom generators. ​ ​ – user6973 Dec 10 '15 at 4:44
• @RickyDemer: See Definitions 4.1-4.3 in the cited paper. If I'm understanding correctly, OWPs imply what they call "crypto-PRGs", but not necessarily what they call "PRGs" in the Glasser-Pavan-Selman-Sengupta paper. For their result, they (seem to) need both OWPs and what they call PRGs. – Joshua Grochow Dec 10 '15 at 5:45
• Kaveh only showed the equivalence to co-NP-complete sets are P-immune, but the conclusion of theorem 4.4 in Glasser et al that all NP-complete sets must have length-increasing reduction, also implies that there are no co-NP-complete P-immune sets. – Lance Fortnow Dec 10 '15 at 13:28
• @JoshuaGrochow Thanks...but are there assumptions we can make which in turn imply the non existence of such a language. I was more interested in scenarios where there is no poly time superset – ARi Dec 26 '15 at 12:38

Interesting question. The statement

for every NP-complete $L$, there is $U$ in P such that $L \subseteq U$ and $U^c$ is infinite.

is equivalent to:

for every NP-complete $L$, complement of $L$ contains an infinite P set.

which is in turn equivalent to

every coNP-complete set contains an infinite P set.

which is by symmetry the same as

every NP-complete set contains an infinite P-set.

I don't think the answer is known. I think natural NP-complete sets satisfy this condition easily. I don't think we have tools to build an artificial set which fails the statement. (see Lance's comment below)

• Your initial statement is trivially true. ​ (Let U be the full language.) ​ ​ ​ ​ – user6973 Dec 9 '15 at 20:10
• Its an interesting chain of deductions...Could you give an example of a natural NP complete language in this regard – ARi Dec 10 '15 at 12:41
• The symmetry doesn't make sense. For example, every c.e. set has an infinite computable subset but there are co-c.e.-sets that don't. – Lance Fortnow Dec 10 '15 at 13:06