6
$\begingroup$

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

$\endgroup$
  • 10
    $\begingroup$ Parity∈NP∖AC0 implies that AC0 is a proper subset of NP. $\endgroup$ – Tsuyoshi Ito Mar 15 '11 at 16:16
  • 9
    $\begingroup$ 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. $\endgroup$ – András Salamon Mar 15 '11 at 17:02
  • 1
    $\begingroup$ ...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.) $\endgroup$ – Antonio E. Porreca Mar 15 '11 at 17:29
  • 3
    $\begingroup$ $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. $\endgroup$ – Robin Kothari Mar 16 '11 at 2:21
  • 2
    $\begingroup$ $\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). $\endgroup$ – Kaveh Mar 16 '11 at 4:20
9
$\begingroup$

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 by M. Agrawal, E. Allender, R. Impagliazzo, T. Pitassi and S. Rudich)

$\endgroup$
  • $\begingroup$ Is it known if there are problems in $AC^0[p]$ or even $AC^0$ that are definitely not NPC? $\endgroup$ – Mitch Mar 17 '11 at 2:26
  • $\begingroup$ @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}$. $\endgroup$ – Kaveh Mar 17 '11 at 11:27
10
$\begingroup$

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

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mitch Mar 17 '11 at 2:33
0
$\begingroup$

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.

$\endgroup$

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.