<p>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.</p>

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

<blockquote>
  <p><strong>Theorem</strong> 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$.</p>
</blockquote>

<p>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 <a href="https://cstheory.stackexchange.com/q/39815/17577">this related question</a>). 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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/a/39816/17577">not recursively presentable and not even countable</a>.
Now, "natural" examples of this are a different story...</p>

CC BY-SA 3.0
2011-09-01T14:28:58.613Z
@Artem: If you consider hardness under log-space reducibility, then every nontrivial language is L-hard.  Therefore, if L=P, there is no languages outside P are P-hard under log-space reducibility.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-01T13:34:31.937Z
I like how this goes through even if $L = P$. Unless I misunderstood something.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-01T09:19:56.477Z
2017-12-21T20:04:11.097Z
2017-12-21T20:04:11.097Z
Ryan Williams
<p>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).</p>

<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. </p>

CC BY-SA 3.0
2011-09-02T12:52:04.273Z
In my opinion, this is almost the same question phrased differently, and it is not necessarily a way to answer the question.  In fact, language A is neither in P nor P-hard if and only if the class of languages reducible to A is incomparable with P (take your favorite notion of reducibility).  As long as the current question is concerned, I think that it is more likely to be useful in the opposite direction; that is, this is another way to interpret the answers to the current question.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-01T14:38:23.783Z
2011-09-01T14:38:23.783Z
Robin Kothari
<p>If $\mathsf{P} \neq \mathsf{L}$ then no sparse set (even a non-computable one) can be $\mathsf{P\text{-}hard}$.</p>

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

CC BY-SA 3.0
2011-09-01T07:18:51.873Z
some the Euler diagrams I've seen of complexity classes have also fed the second misconception for me, which is what I think caused my confusion about X-hardness.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-01T07:56:03.670Z
@Artem, yes, that is also a factor. Here is what I do in the class: I mention the incomparability of $\mod p$ and $\mod q$ under $\mathsf{AC^0}$ reductions, hoping that this would help students avoid thinking that everything is linearly ordered.
Kaveh
CC BY-SA 3.0
2011-09-01T07:58:15.983Z
the total order part I have much fewer problems with. In particular, I think NP and coNP are good enough to show that we shouldn't think of complexity classes having a total order.
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-01T08:05:47.773Z
@Artem, good point (though we can't prove that they are different). I think part of the reason for the terminology is the lack of reasonable lowerbounds, we don't have a good lowerbound for SAT, but we think that it is difficult to solve because it is universal, but the word "universal" doesn't give the same feeling of difficulty as "hard" does, especially to non-experts. But that creates the problem because although one can argue that universality of a problem implies that problem is difficult to solve, the difficulty of solving a problem does not imply that the problem is universal.
Kaveh
CC BY-SA 3.0
2011-09-01T08:09:49.793Z
i.e. universal problems are difficult (at least as difficult as any problem in the class), but difficult problems need not be universal.
Kaveh
CC BY-SA 3.0
2017-12-22T01:04:34.463Z
What’s the definition of “sparse” set here?
Nicola Gigante
CC BY-SA 3.0
2017-12-22T01:20:30.380Z
@gigabytes, https://en.m.wikipedia.org/wiki/Sparse_language
Kaveh
CC BY-SA 3.0
2017-12-22T22:40:08.257Z
I think this is an excellent answer. On a personal level, I didn’t truely get what is expressed here until I studied Turing degrees. Getting used to that context, where the idea of a linear order fails incredibly hard, made me lose some preconceptions about complexity classes.
Stella Biderman
CC BY-SA 3.0
2011-09-01T07:10:27.420Z
2011-09-01T07:18:38.897Z
2011-09-01T07:18:38.897Z
Kaveh
<p>While reading an <a href="https://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard/8021#8021">answer by Peter Shor</a> and an earlier <a href="https://cstheory.stackexchange.com/q/5395/1037">question by Adam Crume</a> I realized that I have some misconceptions about what it means to be $\mathsf{P}$-hard.</p>

<p>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. </p>

<p>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? </p>

<cc.complexity-theory><complexity-classes>
Problems outside of P that are not P-hard
Artem Kaznatcheev
# Problems outside of P that are not P-hard

(Asked by: username_0 on 2011-09-01)

While reading an [answer by Peter Shor](https://cstheory.stackexchange.com/questions/8000/are-the-problems-primes-factoring-known-to-be-p-hard/8021#8021) and an earlier [question by Adam Crume](https://cstheory.stackexchange.com/q/5395/1037) 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?

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


---

## 3 answers

### Answer by username_4 on 2011-09-01. Score: 19 | Accepted answer

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

> **Comments:**
> **username_0**: some the Euler diagrams I've seen of complexity classes have also fed the second misconception for me, which is what I think caused my confusion about X-hardness.  
> **username_4**: @Artem, yes, that is also a factor. Here is what I do in the class: I mention the incomparability of $\mod p$ and $\mod q$ under $\mathsf{AC^0}$ reductions, hoping that this would help students avoid thinking that everything is linearly ordered.  
> **username_0**: the total order part I have much fewer problems with. In particular, I think NP and coNP are good enough to show that we shouldn't think of complexity classes having a total order.  
> **username_4**: @Artem, good point (though we can't prove that they are different). I think part of the reason for the terminology is the lack of reasonable lowerbounds, we don't have a good lowerbound for SAT, but we think that it is difficult to solve because it is universal, but the word "universal" doesn't give the same feeling of difficulty as "hard" does, especially to non-experts. But that creates the problem because although one can argue that universality of a problem implies that problem is difficult to solve, the difficulty of solving a problem does not imply that the problem is universal.  
> **username_4**: i.e. universal problems are difficult (at least as difficult as any problem in the class), but difficult problems need not be universal.  
> **username_5**: What’s the definition of “sparse” set here?  
> **username_4**: @gigabytes, https://en.m.wikipedia.org/wiki/Sparse_language  
> **username_6**: I think this is an excellent answer. On a personal level, I didn’t truely get what is expressed here until I studied Turing degrees. Getting used to that context, where the idea of a linear order fails incredibly hard, made me lose some preconceptions about complexity classes.  

---

### Answer by username_1 on 2011-09-01. Score: 20

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](https://cstheory.stackexchange.com/q/39815/17577)). 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](https://cstheory.stackexchange.com/a/39816/17577).
Now, "natural" examples of this are a different story...

> **Comments:**
> **username_0**: I like how this goes through even if $L = P$. Unless I misunderstood something.  
> **username_2**: @Artem: If you consider hardness under log-space reducibility, then every nontrivial language is L-hard.  Therefore, if L=P, there is no languages outside P are P-hard under log-space reducibility.  

---

### Answer by username_3 on 2011-09-01. Score: 11

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.

> **Comments:**
> **username_2**: In my opinion, this is almost the same question phrased differently, and it is not necessarily a way to answer the question.  In fact, language A is neither in P nor P-hard if and only if the class of languages reducible to A is incomparable with P (take your favorite notion of reducibility).  As long as the current question is concerned, I think that it is more likely to be useful in the opposite direction; that is, this is another way to interpret the answers to the current question.  

---

