15

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

Community
  • 1
ARi
  • 405
  • 2
  • 8
  • 5
    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 05 '15 at 20:32
  • 3
    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 05:01

2 Answers2

10

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • ECCC draft – Kaveh Dec 09 '15 at 20:57
  • By strong hard-core functions (and iteration), one-way permutations imply pseudorandom generators. ​ ​ –  Dec 10 '15 at 04:44
  • 1
    @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 05:45
  • 6
    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
  • Please see my answer on above lines http://cstheory.stackexchange.com/a/33450/17763 – ARi Dec 27 '15 at 11:52
5

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)

Kaveh
  • 21,577
  • 8
  • 82
  • 183
  • Your initial statement is trivially true. ​ (Let U be the full language.) ​ ​ ​ ​ –  Dec 09 '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
  • 3
    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