<p>[Answering the original motivating issue: "Should I just accept the first statement since NPC is defined with respect to deterministic polytime reductions?"]</p>

<p>First, if $P=NP$ but the Berman-Hartmanis Isomorphism Conjecture fails, then there are infinitely many distinct p-isomorphism classes of languages within $P$. So even though it is true that $P=NP$ implies all sets in $P$ are $NP$-complete with respect to polynomial-time reduction (technical caveat below), that does not mean that we lose all information about $P$. By looking at a finer type of reduction -- but still polynomial-time, namely polynomial-time computable-and-invertible length-increasing one-one reductions -- we can potentially tell a lot about what's going on inside $P$.</p>

<p>In fact, if $P=NP$ but the Isomorphism Conjecture fails, then the partially ordered set of p-isomorphism classes inside $P$ is quite rich: any countable partial order can be embedded in it (see <a href="http://dx.doi.org/10.1145/800061.808770">P. Young. Some structural properties of polynomial reducibilities and sets in NP. STOC 1983.</a>). </p>

<p>But more generally, in some cases it does feel wrong to lump all of $P$ together and in other cases it's exactly what you want. This is why, for example, we don't use poly-time reductions when discussing $L$ versus $P$, but we do when discussing $P$ versus $NP$. But there might be another class you want to contrast with $NP$ where it makes sense to use other reductions. The type of reduction you use should be the type you need for the problem at hand; there is no "single right reduction" to define, e.g., $NP$-completeness (though "$NP$-complete" without qualification usually means w.r.t. poly-time many-one reductions, but that is a matter of convention).</p>

<p>Distinctness of complexity classes is not parametrized by reductions; however, there are several potentially distinct classes that could legitimately be called "$NP$-complete," namely for any reducibility $r$, "$NP$-complete with respect to $r$-reductions".</p>

<p>(Caveat: If we use poly-time many-one reductions, then $\emptyset$ and $\Sigma^{*}$ do not become $NP$-complete if $P=NP$. If we use poly-time Turing reductions, or even poly-time 1-tt reductions, they do.)</p>

CC BY-SA 2.5
2011-03-17T02:33:15.677Z
It's funny but my actual motivating question is not the 'if P=NP, then P=NPC', rather the strictness separation of classes in the hierarchy. And your answer helps with both.
Mitch
CC BY-SA 2.5
2011-03-16T16:11:20.180Z
2011-03-16T16:11:20.180Z
Joshua Grochow
<p>Both the (current) answers plus the comments answer all together. I thought I'd summarize here.</p>

<ul>
<li><p>Completeness for a class is defined variably with respect to a given class; for example, NPC is usually defined wrt detpolytime (P) reductions, but sometimes also L (logspace) or even DLOGTIME (and SAT is NPC for all of these).</p></li>
<li><p>There are known nontrivial proper subclasses of NP ($AC^0[p]$).</p></li>
</ul>

<p>So the claim made in the first sentence of my OP is true, but only with the common assumption of P-reductions. </p>

CC BY-SA 2.5
2011-03-20T16:17:22.403Z
2011-03-20T16:17:22.403Z
Mitch
<p>Reposting my comment as an answer:</p>

<p>AC<sup>0</sup>[p] is strict subset of NP, where AC<sup>0</sup>[p] is AC<sup>0</sup> with mod p gates, and p is a prime. </p>

<p>As for whether we can define NP-completeness to make it stricter, you can define it w.r.t., say, logspace reductions or even ACC reductions. As far as I know, it is not known if this changes the class NPC. What is known, however, is that AC<sup>0</sup> reductions are not powerful enough. (Ref: <a href="http://www.springerlink.com/content/bbar426549dv33ut/" rel="noreferrer">Reducing the complexity of reductions</a> by M. Agrawal, E. Allender, R. Impagliazzo, T. Pitassi and S. Rudich)</p>

CC BY-SA 2.5
2011-03-17T02:26:08.210Z
Is it known if there are problems in $AC^0[p]$ or even $AC^0$ that are definitely not NPC?
Mitch
CC BY-SA 2.5
2011-03-17T11:27:43.110Z
@Mitch, yes (under suitable reductions), an $\mathbf{NP}$ problem can be reduced to an $\mathbf{NPC}$ problem, so these classes being different from $\mathbf{NP}$ implies that they also different from $\mathbf{NPC}$, i.e. non of them is $\mathbf{NPC}$. On the other hand, if you are using $\mathbf{P}$ reductions, then as long as it is possible to have $\mathbf{P=NP}$, all problems in $\mathbf{P}$ including those in these classes will be $\mathbf{NPC}$.
Kaveh
CC BY-SA 2.5
2011-03-16T13:57:39.810Z
2011-03-16T13:57:39.810Z
Robin Kothari
<p>It has been claimed that if $P = NP$, then every problem in $P$ (equivalently $NP$) is NP-complete. </p>

<p>As a blanket statement, I find this wrong because, well, there's the trivial problem or constant time problems, but more interestingly, I expect that there are classes that are very small that are provably not NP-complete but aren't entirely trivial. This is in analogy to the fact that it is known that $P != EXP$, there must be a $C \subsetneq NP$, presumably $C= NTIME(\log(n))$. But I have never heard discussed such a small class.</p>

<p>The smallest well-known class I can think of is $AC^0$, but I don't know whether it is known that it is not $NPC$. And there's Ryan's recent result that $NEXP \not\subset ACC^0$, which leads me to believe that it would have to be a much smaller class than $AC^0$ that would be known to be disctinct from $NP$.</p>

<p>I think the first statement might be considered to be true if all one has are deterministic polytime reductions (which would imply that -all- problems in $P$ are $P$-complete), but that seems to be too simplistic. A particular proof might use a particular reduction, but the distinctness of complexity classes is not parameterized by those reductions (or is it?).</p>

<p>So, thoughts/suggestions? Should I just accept the first statement since $NPC$ is defined with respect to deterministic polytime reductions? And even so, is there a well-known non-trivial class that is provably a proper subset of $NP$?</p>

CC BY-SA 2.5
2011-03-15T16:16:04.947Z
Parity∈NP∖AC0 implies that AC0 is a proper subset of NP.
Tsuyoshi Ito
CC BY-SA 2.5
2011-03-15T16:31:17.520Z
Even closer, Parity∈ACC0 so AC0 is a proper subset of ACC0. Are there described classes between AC0 and ACC0 that might be relevant?
Mitch
CC BY-SA 2.5
2011-03-15T17:02:31.303Z
If P=NP then the power of the class is fully in the polynomial-time reduction, so the problem you are reducing to can be as trivial as you wish.
András Salamon
CC BY-SA 2.5
2011-03-15T17:29:52.457Z
...as long as it isn't the empty set or the set of all strings, to be pedantic. (The other constant-time solvable problems are fine though.)
Antonio E. Porreca
CC BY-SA 2.5
2011-03-15T17:50:07.107Z
@Antonio: You are right of course, one needs at least one "yes" and one "no" instance for the reduction to preserve structure.
András Salamon
CC BY-SA 2.5
2011-03-15T17:57:34.463Z
@Antonio, @András: Can NP-completeness (with P reductions) be preserved using DLOGTIME reductions instead (or even more restricted reductions)? It just seems wrong to lump all the problems in P together.
Mitch
CC BY-SA 2.5
2011-03-15T23:18:24.407Z
@Philip: I'm not sure what of many things 'the answer is probably not' is referring to and in what direction.
Mitch
CC BY-SA 2.5
2011-03-16T02:21:35.680Z
$AC^0$[p] is strict subset of NP, where $AC^0$[p] is $AC^0$ with mod p gates, and p is a prime. As for whether we can define NP-completeness to make it stricter, you can define it w.r.t., say, logspace reductions or even ACC reductions. As far as I know, it is not known if this changes the class NPC.
Robin Kothari
CC BY-SA 2.5
2011-03-16T04:20:13.060Z
$\mathbf{SAT}$ is $\mathbf{NPC}$ even w.r.t. $\mathbf{DLogTime}$ reductions. I don't know what you mean by a reduction weaker than $\mathbf{DLogTime}$. It is so weak that it is not an interesting complexity class (it is strictly contained in $\mathbf{AC^0}$ which is equal to logarithmic-time hierarchy).
Kaveh
CC BY-SA 2.5
2011-03-16T08:03:01.273Z
It is open if $\mathbf{ACC^0}$ is equal to $\mathbf{NP}$ so any class containing it will be open. So I think Robin's answer is the largest well-known class properly inside $\mathbf{NP}$.
Kaveh
CC BY-SA 2.5
2011-03-16T08:10:58.363Z
@Robin, I think your comment is an answer.
Kaveh
CC BY-SA 2.5
2011-03-22T04:28:04.050Z
Due to the non-deterministic time hierarchy theorem, any $NTIME( p(n)$ , where $p(n)$ is a polynomial, is a proper subset of $NP$ but I guess due to the formulation of your question you are not interested in $NTIME$.
chazisop
<cc.complexity-theory>
Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset?
Mitch
# Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset?

(Asked by: username_0 on 2011-03-15)

It has been claimed that if $P = NP$, then every problem in $P$ (equivalently $NP$) is NP-complete.

As a blanket statement, I find this wrong because, well, there's the trivial problem or constant time problems, but more interestingly, I expect that there are classes that are very small that are provably not NP-complete but aren't entirely trivial. This is in analogy to the fact that it is known that $P != EXP$, there must be a $C \subsetneq NP$, presumably $C= NTIME(\log(n))$. But I have never heard discussed such a small class.

The smallest well-known class I can think of is $AC^0$, but I don't know whether it is known that it is not $NPC$. And there's Ryan's recent result that $NEXP \not\subset ACC^0$, which leads me to believe that it would have to be a much smaller class than $AC^0$ that would be known to be disctinct from $NP$.

I think the first statement might be considered to be true if all one has are deterministic polytime reductions (which would imply that -all- problems in $P$ are $P$-complete), but that seems to be too simplistic. A particular proof might use a particular reduction, but the distinctness of complexity classes is not parameterized by those reductions (or is it?).

So, thoughts/suggestions? Should I just accept the first statement since $NPC$ is defined with respect to deterministic polytime reductions? And even so, is there a well-known non-trivial class that is provably a proper subset of $NP$?

**Tags:** cc.complexity-theory

> **Comments:**
> **username_1**: Parity∈NP∖AC0 implies that AC0 is a proper subset of NP.  
> **username_0**: Even closer, Parity∈ACC0 so AC0 is a proper subset of ACC0. Are there described classes between AC0 and ACC0 that might be relevant?  
> **username_2**: If P=NP then the power of the class is fully in the polynomial-time reduction, so the problem you are reducing to can be as trivial as you wish.  
> **username_3**: ...as long as it isn't the empty set or the set of all strings, to be pedantic. (The other constant-time solvable problems are fine though.)  
> **username_2**: @Antonio: You are right of course, one needs at least one "yes" and one "no" instance for the reduction to preserve structure.  
> **username_0**: @Antonio, @András: Can NP-completeness (with P reductions) be preserved using DLOGTIME reductions instead (or even more restricted reductions)? It just seems wrong to lump all the problems in P together.  
> **username_0**: @Philip: I'm not sure what of many things 'the answer is probably not' is referring to and in what direction.  
> **username_4**: $AC^0$[p] is strict subset of NP, where $AC^0$[p] is $AC^0$ with mod p gates, and p is a prime. As for whether we can define NP-completeness to make it stricter, you can define it w.r.t., say, logspace reductions or even ACC reductions. As far as I know, it is not known if this changes the class NPC.  
> **username_5**: $\mathbf{SAT}$ is $\mathbf{NPC}$ even w.r.t. $\mathbf{DLogTime}$ reductions. I don't know what you mean by a reduction weaker than $\mathbf{DLogTime}$. It is so weak that it is not an interesting complexity class (it is strictly contained in $\mathbf{AC^0}$ which is equal to logarithmic-time hierarchy).  
> **username_5**: It is open if $\mathbf{ACC^0}$ is equal to $\mathbf{NP}$ so any class containing it will be open. So I think Robin's answer is the largest well-known class properly inside $\mathbf{NP}$.  
> **username_5**: @Robin, I think your comment is an answer.  
> **username_6**: Due to the non-deterministic time hierarchy theorem, any $NTIME( p(n)$ , where $p(n)$ is a polynomial, is a proper subset of $NP$ but I guess due to the formulation of your question you are not interested in $NTIME$.  

---

## 3 answers

### Answer by username_4 on 2011-03-16. Score: 10 | Accepted answer

Reposting my comment as an answer:

AC0[p] is strict subset of NP, where AC0[p] is AC0 with mod p gates, and p is a prime.

As for whether we can define NP-completeness to make it stricter, you can define it w.r.t., say, logspace reductions or even ACC reductions. As far as I know, it is not known if this changes the class NPC. What is known, however, is that AC0 reductions are not powerful enough. (Ref: [Reducing the complexity of reductions](http://www.springerlink.com/content/bbar426549dv33ut/) by M. Agrawal, E. Allender, R. Impagliazzo, T. Pitassi and S. Rudich)

> **Comments:**
> **username_0**: Is it known if there are problems in $AC^0[p]$ or even $AC^0$ that are definitely not NPC?  
> **username_5**: @username_0, yes (under suitable reductions), an $\mathbf{NP}$ problem can be reduced to an $\mathbf{NPC}$ problem, so these classes being different from $\mathbf{NP}$ implies that they also different from $\mathbf{NPC}$, i.e. non of them is $\mathbf{NPC}$. On the other hand, if you are using $\mathbf{P}$ reductions, then as long as it is possible to have $\mathbf{P=NP}$, all problems in $\mathbf{P}$ including those in these classes will be $\mathbf{NPC}$.  

---

### Answer by username_7 on 2011-03-16. Score: 10

[Answering the original motivating issue: "Should I just accept the first statement since NPC is defined with respect to deterministic polytime reductions?"]

First, if $P=NP$ but the Berman-Hartmanis Isomorphism Conjecture fails, then there are infinitely many distinct p-isomorphism classes of languages within $P$. So even though it is true that $P=NP$ implies all sets in $P$ are $NP$-complete with respect to polynomial-time reduction (technical caveat below), that does not mean that we lose all information about $P$. By looking at a finer type of reduction -- but still polynomial-time, namely polynomial-time computable-and-invertible length-increasing one-one reductions -- we can potentially tell a lot about what's going on inside $P$.

In fact, if $P=NP$ but the Isomorphism Conjecture fails, then the partially ordered set of p-isomorphism classes inside $P$ is quite rich: any countable partial order can be embedded in it (see [P. Young. Some structural properties of polynomial reducibilities and sets in NP. STOC 1983.](http://dx.doi.org/10.1145/800061.808770)).

But more generally, in some cases it does feel wrong to lump all of $P$ together and in other cases it's exactly what you want. This is why, for example, we don't use poly-time reductions when discussing $L$ versus $P$, but we do when discussing $P$ versus $NP$. But there might be another class you want to contrast with $NP$ where it makes sense to use other reductions. The type of reduction you use should be the type you need for the problem at hand; there is no "single right reduction" to define, e.g., $NP$-completeness (though "$NP$-complete" without qualification usually means w.r.t. poly-time many-one reductions, but that is a matter of convention).

Distinctness of complexity classes is not parametrized by reductions; however, there are several potentially distinct classes that could legitimately be called "$NP$-complete," namely for any reducibility $r$, "$NP$-complete with respect to $r$-reductions".

(Caveat: If we use poly-time many-one reductions, then $\emptyset$ and $\Sigma^{\*}$ do not become $NP$-complete if $P=NP$. If we use poly-time Turing reductions, or even poly-time 1-tt reductions, they do.)

> **Comments:**
> **username_0**: It's funny but my actual motivating question is not the 'if P=NP, then P=NPC', rather the strictness separation of classes in the hierarchy. And your answer helps with both.  

---

### Answer by username_0 on 2011-03-20. Score: 0

Both the (current) answers plus the comments answer all together. I thought I'd summarize here.

* Completeness for a class is defined variably with respect to a given class; for example, NPC is usually defined wrt detpolytime (P) reductions, but sometimes also L (logspace) or even DLOGTIME (and SAT is NPC for all of these).
* There are known nontrivial proper subclasses of NP ($AC^0[p]$).

So the claim made in the first sentence of my OP is true, but only with the common assumption of P-reductions.


---

