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$.


migrated from cs.stackexchange.com Dec 9 '15 at 16:26

This question came from our site for students, researchers and practitioners of computer science.

  • 5
    $\begingroup$ 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$. $\endgroup$ – Marzio De Biasi Dec 5 '15 at 20:32
  • 3
    $\begingroup$ How about the relativized version: Is there an oracle $A$ s.t. all co-NP$^A$ sets are P$^A$-immune. $\endgroup$ – Lance Fortnow Dec 10 '15 at 13:41
  • $\begingroup$ @LanceFortnow ...or for any complete language in a particular. Complexity class, is there always a non trivial superset of a lesser complexity. $\endgroup$ – 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.)

  • $\begingroup$ ECCC draft $\endgroup$ – Kaveh Dec 9 '15 at 20:57
  • $\begingroup$ By strong hard-core functions (and iteration), one-way permutations imply pseudorandom generators. ​ ​ $\endgroup$ – user6973 Dec 10 '15 at 4:44
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Dec 10 '15 at 5:45
  • 6
    $\begingroup$ 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. $\endgroup$ – Lance Fortnow Dec 10 '15 at 13:28
  • $\begingroup$ @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 $\endgroup$ – 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)

  • $\begingroup$ Your initial statement is trivially true. ​ (Let U be the full language.) ​ ​ ​ ​ $\endgroup$ – user6973 Dec 9 '15 at 20:10
  • $\begingroup$ Its an interesting chain of deductions...Could you give an example of a natural NP complete language in this regard $\endgroup$ – ARi Dec 10 '15 at 12:41
  • 3
    $\begingroup$ 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. $\endgroup$ – Lance Fortnow Dec 10 '15 at 13:06

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.