Problems outside of P that are not P-hard

Question

While reading an answer by Peter Shor and an earlier question by Adam Crume I realized that I have some misconceptions about what it means to be $\mathsf{P}$-hard.

A problem is $\mathsf{P}$-hard if any problem in $\mathsf{P}$ is reducible to it with $\mathsf{L}$ (or if you prefer $\mathsf{NC}$) reductions. A problem is outside of $\mathsf{P}$ if there does not exist a polynomial time algorithm to solve it. This means that there should be problem that are outside $\mathsf{P}$ but are not $\mathsf{P}$-hard. If we asume that FACTORING is outside of $\mathsf{P}$, then Peter Shor's answer suggests that FACTORING could be such a problem.

Are there any known problems (natural or artificial) that are known to lay outside $\mathsf{P}$ but not be $\mathsf{P}$-hard? What about under assumptions weaker than the factoring assumption? Is there a name for this complexity class?

Answer 1

If $\mathsf{P} \neq \mathsf{L}$ then no sparse set (even a non-computable one) can be $\mathsf{P\text{-}hard}$.

The misconception comes from thinking about complexity classes (and computational problems) as creating a linear order which is not true. Using the word "hardness" for a problem can be used to solve other problems in the class also contributes to the misconception. A lowerbound for a problem (i.e. not being in a complexity class) does not imply that the problem is hard for the class (i.e. can be used to solve other problems in the class). I don't know if there is better alternative terminology for "hardness" that is in use currently, one that has been used in previous decades is "universality" (which, IMHO, expressed the concept more faithfully, and then we could have used "hardness" for not being in the class, but changing established terminology is very difficult).

Answer 2

I think you can construct a set not in $P$ that is not $P$-hard by a Ladner-style argument. Here's a specific example.

In his paper "A Uniform Approach to Obtain Diagonal Sets in Complexity Classes" (Theor. Comp. Sci. 18, 1982), Schöning proves the following:

Theorem Suppose $A_1 \notin C_1$, $A_2 \notin C_2$, $C_1$ and $C_2$ are recursively presentable complexity classes and are closed under finite variations. Then there's a set $A$ such that $A \notin C_1$, $A \notin C_2$, and if $A_1 \in P$ and $A_2$ is not trivial (empty set or all strings) then $A$ is polytime many-one reducible to $A_2$.

To apply this, set $A_1$ to be the empty set, and $A_2$ to be $EXP$-complete under polytime reductions, set $C_1$ be the set of $P$-hard sets that are in $EXP$, set $C_2 = P$. The empty set cannot be $P$-hard (the definition of $P$-hardness for a language requires that there is at least one instance in the language and one instance not in). $A_2$ is definitely not in $C_2$. The $C_1$ and $C_2$ can be verified to meet the above conditions (similar to how Schoening does it for the $NP$-complete sets; see also this related question). So we get an $A$ that is not a $P$-hard problem in $EXP$, and that $A$ is not in $P$. But because $A_1 \in P$ and $A_2$ is nontrivial, $A$ is many-one reducible to an $EXP$-complete set, so it is in $EXP$. Therefore, in particular, $A$ cannot be $P$-hard either.

In the above argument, the restriction to $P$-hard problems in $EXP$ is necessary to ensure recursive presentability, since the P-hard problems as a whole are not recursively presentable and not even countable. Now, "natural" examples of this are a different story...

Answer 3

Another way to generate problems that are outside P but not P-hard is to take complete problems for classes incomparable with P. Say a class X is incomparable with P, in the sense that neither is a subset of the other. Then a X-complete problem is necessarily outside P (otherwise P would include X) and is not P-hard (otherwise X would include P).

I tried to think of some classes incomparable with P, but P is a pretty robust class, so there aren't too many such classes. For example, RNC and QNC might be incomparable with P. DSPACE($\log^2$) might also be incomparable with P. PolyL is incomparable with P, but doesn't have complete problems under logspace reductions.