<p>I don't know whether you are asking an open problem, or whether it has already been resolved. Yet the following paper can shed some light on this problem:</p>

<p>Kurtz, S. A. 1985. Sparse sets in NP-P: relativizations. <em>SIAM J. Comput.</em> 14, 1 (Feb. 1985), 113-119. DOI= <a href="http://dx.doi.org/10.1137/0214008" rel="noreferrer">http://dx.doi.org/10.1137/0214008</a></p>

<p>Basically, it states that, even assuming P≠NP, there is an oracle relative to which no sparse sets in NP-P exists. </p>

<p>On the other hand, the following paper:</p>

<p>T. Baker, J. Gill, and R. Solovay, "Relativizations of the P=?NP Question", <em>SIAM J. Computing</em> (1975), 431-442. DOI= <a href="http://dx.doi.org/10.1137/0204037" rel="noreferrer">http://dx.doi.org/10.1137/0204037</a></p>

<p>demonstrates an oracle relative to which sparse sets in NP-P exists.</p>

<p>Since $NPI \subset NP-P$, this proves that, either way, the proof does not relativize.</p>

<p><strong>EDIT:</strong> In addition, there exist sparse sets in NP-P if and only if $E \neq NE$:</p>

<p>Hartmanis, J., Sewelson, V., and Immerman, N. 1983. Sparse sets in NP-P: Exptime versus nexptime. In <em>Proceedings of the Fifteenth Annual ACM Symposium on theory of Computing STOC '83</em>. ACM, New York, NY, 382-391. DOI= <a href="http://doi.acm.org/10.1145/800061.808769" rel="noreferrer">http://doi.acm.org/10.1145/800061.808769</a></p>

<p>(Journal version available here: <a href="http://dx.doi.org/10.1016/S0019-9958(85)80004-8" rel="noreferrer">http://dx.doi.org/10.1016/S0019-9958(85)80004-8</a>)</p>

CC BY-SA 2.5
2010-09-27T11:42:55.727Z
To state HIS correctly: There are sparse sets in NP-P iff E \neq NE. They used different notation back then.
Lance Fortnow
CC BY-SA 2.5
2010-09-27T11:47:15.727Z
Thanks Lance. I didn't know that. I'll correct the answer in a minute.
Sadeq Dousti
CC BY-SA 2.5
2010-09-27T06:54:25.697Z
2010-09-27T11:48:23.520Z
2010-09-27T11:48:23.520Z
Sadeq Dousti
<p>I wonder to know wether there are sparse language (even constructed by delayed diagolanization) in NPI under the assumption that $P \neq NP$.</p>

<cc.complexity-theory><complexity-classes>
Is there any sparse language known to be in NPI under the $P \neq NP$ assumption ?
Ludovic Patey
# Is there any sparse language known to be in NPI under the $P \neq NP$ assumption ?

(Asked by: username_0 on 2010-09-27)

I wonder to know wether there are sparse language (even constructed by delayed diagolanization) in NPI under the assumption that $P \neq NP$.

**Tags:** cc.complexity-theory, complexity-classes

---

## 1 answers

### Answer by username_1 on 2010-09-27. Score: 13 | Accepted answer

I don't know whether you are asking an open problem, or whether it has already been resolved. Yet the following paper can shed some light on this problem:

Kurtz, S. A. 1985. Sparse sets in NP-P: relativizations. *SIAM J. Comput.* 14, 1 (Feb. 1985), 113-119. DOI= <http://dx.doi.org/10.1137/0214008>

Basically, it states that, even assuming P≠NP, there is an oracle relative to which no sparse sets in NP-P exists.

On the other hand, the following paper:

T. Baker, J. Gill, and R. Solovay, "Relativizations of the P=?NP Question", *SIAM J. Computing* (1975), 431-442. DOI= <http://dx.doi.org/10.1137/0204037>

demonstrates an oracle relative to which sparse sets in NP-P exists.

Since $NPI \subset NP-P$, this proves that, either way, the proof does not relativize.

**EDIT:** In addition, there exist sparse sets in NP-P if and only if $E \neq NE$:

Hartmanis, J., Sewelson, V., and Immerman, N. 1983. Sparse sets in NP-P: Exptime versus nexptime. In *Proceedings of the Fifteenth Annual ACM Symposium on theory of Computing STOC '83*. ACM, New York, NY, 382-391. DOI= <http://doi.acm.org/10.1145/800061.808769>

(Journal version available here: <http://dx.doi.org/10.1016/S0019-9958(85)80004-8>)

> **Comments:**
> **username_2**: To state HIS correctly: There are sparse sets in NP-P iff E \neq NE. They used different notation back then.  
> **username_1**: Thanks Lance. I didn't know that. I'll correct the answer in a minute.  

---

