22
$\begingroup$

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?

$\endgroup$
18
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Artem Kaznatcheev Sep 1 '11 at 7:18
  • $\begingroup$ @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. $\endgroup$ – Kaveh Sep 1 '11 at 7:56
  • 1
    $\begingroup$ 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. $\endgroup$ – Artem Kaznatcheev Sep 1 '11 at 7:58
  • 1
    $\begingroup$ @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. $\endgroup$ – Kaveh Sep 1 '11 at 8:05
  • 3
    $\begingroup$ i.e. universal problems are difficult (at least as difficult as any problem in the class), but difficult problems need not be universal. $\endgroup$ – Kaveh Sep 1 '11 at 8:09
19
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I like how this goes through even if $L = P$. Unless I misunderstood something. $\endgroup$ – Artem Kaznatcheev Sep 1 '11 at 13:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Sep 1 '11 at 14:28
10
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 2 '11 at 12:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.