<p>Interesting question. 
The statement </p>

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

<p>is equivalent to:</p>

<blockquote>
  <p>for every NP-complete $L$, complement of $L$ contains an infinite P set. </p>
</blockquote>

<p>which is in turn equivalent to </p>

<blockquote>
  <p>every coNP-complete set contains an infinite P set. </p>
</blockquote>

<p><strike>which is by symmetry the same as </p>

<blockquote>
  <p>every NP-complete set contains an infinite P-set.</p>
</blockquote>

<p>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.
</strike> (see Lance's comment below)</p>

CC BY-SA 3.0
2015-12-10T12:41:14.160Z
Its an interesting chain of deductions...Could you give an example of a natural NP complete language in this regard
ARi
CC BY-SA 3.0
2015-12-10T13:06:25.403Z
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
CC BY-SA 3.0
2015-12-09T19:48:21.993Z
2015-12-10T15:23:14.243Z
2015-12-10T15:23:14.243Z
Kaveh
<p>Every $\mathsf{coNP}$-complete set contains an infinite subset in $\mathsf{P}$ assuming that </p>

<ul>
<li>pseudorandom generators exist, and </li>
<li>secure one-way permutations exist.</li>
</ul>

<p>In other words, assuming that these two conjectures are true, 
no $\mathsf{coNP}$-complete set is P-<a href="https://en.wikipedia.org/wiki/Simple_set" rel="nofollow">immune</a>.
As pointed out in the comments by Lance, 
this is implied by Theorem 4.4 of </p>

<ul>
<li>Glasser, Pavan, Selman, and Sengupta, "<a href="http://epubs.siam.org/doi/abs/10.1137/S009753970444421X" rel="nofollow">Properties of NP-complete sets</a>",
SIAM J. Comput. 36(2), 516–542.</li>
</ul>

<p>(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.)</p>

CC BY-SA 3.0
2015-12-09T20:57:24.840Z
[ECCC draft](http://eccc.hpi-web.de/report/2004/019/)
Kaveh
CC BY-SA 3.0
2015-12-10T05:45:10.383Z
@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
CC BY-SA 3.0
2015-12-10T13:28:42.000Z
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
CC BY-SA 3.0
2015-12-26T12:38:03.103Z
@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
CC BY-SA 3.0
2015-12-27T11:52:16.453Z
Please see my answer on above lines http://cstheory.stackexchange.com/a/33450/17763
ARi
CC BY-SA 3.0
2015-12-09T20:43:55.457Z
2015-12-24T17:49:14.767Z
2015-12-24T17:49:14.767Z
Joshua Grochow
<p>For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite?</p>

<p>A trivial version which does not stipulate the superset to have infinite complement has been asked at <a href="https://cs.stackexchange.com/q/50123/42961">https://cs.stackexchange.com/q/50123/42961</a></p>

<p>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 &gt; 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$.</p>

CC BY-SA 3.0
2015-12-05T20:32:06.003Z
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
CC BY-SA 3.0
2015-12-10T13:41:16.677Z
How about the relativized version: Is there an oracle $A$ s.t. all co-NP$^A$ sets are P$^A$-immune.
Lance Fortnow
CC BY-SA 3.0
2015-12-11T05:01:58.780Z
@LanceFortnow ...or for any complete language in a particular. Complexity class, is there always a non trivial superset of a lesser complexity.
ARi
<cc.complexity-theory><np-complete><structural-complexity>
Poly time superset of NP complete language with infinitely many strings excluded from it
ARi
# Poly time superset of NP complete language with infinitely many strings excluded from it

(Asked by: username_0 on 2015-12-05)

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

**Tags:** cc.complexity-theory, np-complete, structural-complexity
> **Comments:**
> **username_1**: 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$.  
> **username_2**: How about the relativized version: Is there an oracle $A$ s.t. all co-NP$^A$ sets are P$^A$-immune.  
> **username_0**: @LanceFortnow ...or for any complete language in a particular. Complexity class, is there always a non trivial superset of a lesser complexity.  

---

## 2 answers

### Answer by username_4 on 2015-12-09. Score: 10 | Accepted answer

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](https://en.wikipedia.org/wiki/Simple_set).
As pointed out in the comments by Lance,
this is implied by Theorem 4.4 of

* Glasser, Pavan, Selman, and Sengupta, "[Properties of NP-complete sets](http://epubs.siam.org/doi/abs/10.1137/S009753970444421X)",
  SIAM J. Comput. 36(2), 516–542.

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

> **Comments:**
> **username_3**: [ECCC draft](http://eccc.hpi-web.de/report/2004/019/)  
> **username_4**: @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.  
> **username_2**: 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.  
> **username_0**: @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  
> **username_0**: Please see my answer on above lines http://cstheory.stackexchange.com/a/33450/17763  

---

### Answer by username_3 on 2015-12-09. Score: 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)

> **Comments:**
> **username_0**: Its an interesting chain of deductions...Could you give an example of a natural NP complete language in this regard  
> **username_2**: 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.  

---

