Is there a well-known nontrivial subset of NP for which it is known that it is a proper subset?

Question

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

Answer 1

Reposting my comment as an answer:

AC⁰[p] is strict subset of NP, where AC⁰[p] is AC⁰ 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 AC⁰ reductions are not powerful enough. (Ref: Reducing the complexity of reductions by M. Agrawal, E. Allender, R. Impagliazzo, T. Pitassi and S. Rudich)

Answer 2

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

Answer 3

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.