3
$\begingroup$

My question is specifically about $\emptyset$, but more generally about any language that can be decided in (deterministic or nondeterministic doesn't really make a difference here) constant time. Obviously, $\emptyset$ cannot be $\mathsf{NP}$-hard since there is nothing to map "yes"-instances to, but I'd prefer a one line argument using a time hierarchy theorem, ideally. Currently I'm arguing (very informally speaking) that since constant time is $\subsetneq \mathbb{o}(n \log n)$, constant time is strictly "less powerful" than any deterministic polynomial time due to the deterministic time hierarchy theorem and thus - since $$\mathsf{Polytime}(f(n)) \subseteq \mathsf{NPolytime}(f(n))$$ - also strictly less powerful than nondeterministic polynomial time. So, constant time languages can't be $\mathsf{NP}$-hard.

This doesn't sound elegant to me at all (although it should be correct I hope, even if not phrased as formally as I'd write it down for something to hand in). What's the most elegant argument you can come up with, preferably using not-too-advanced complexity theory?

$\endgroup$
  • $\begingroup$ Thinking a bit about it, it seems to me that for any $L \neq \emptyset$, this may actually depend on whether $\mathsf{P} = \mathsf{NP}$ since if $\mathsf{P} = \mathsf{NP}$, we can just reduce any problem in $\mathsf{NP}$ to a problem solvable in det. polytime, then solve that problem deterministically, and map to some $x \in L$ iff we have a "yes"-instance of the original problem. The reduction would be in det. polytime, rendering $L$ $\mathsf{NP}$-hard. This sounds very counterintuitive, though. $\endgroup$ – G. Bach May 19 '14 at 13:55
5
$\begingroup$

Let $L \in P$ be non-trivial (not empty and not containing everything). If $L$ is NP-hard then $P=NP$. Indeed, given any language $L' \in NP$, by definition of NP-hardness there is a polytime reduction $f$ such that $x \in L'$ iff $f(x) \in L$. Since $L \in P$, this gives a polytime algorithm for $L'$, showing that $L' \in P$.

Conversely, if $P=NP$ then $L$ is NP-hard. Indeed, given $L' \in NP$, we can decide $L'$ in polynomial time using some algorithm $A$. Fix some yes instance and some no instance of $L$, and use $A$ to come up with a polytime reduction from $L'$ to $L$, which always returns one of the two fixed instances. This shows that $L$ is NP-hard.

Summarizing, if $L \in P$ is non-trivial then $L$ is NP-hard iff $P=NP$.

$\endgroup$
  • $\begingroup$ Yeah, that's what I figured; basically, if $\mathsf{P} = \mathsf{NP}$, then all the power we need to prove $\mathsf{NP}$-hardness is already in the reduction, so the question of how complex the problem we want to reduce to is becomes irrelevant as long as there is at least one "yes" and one "no" instance. Thanks! $\endgroup$ – G. Bach May 19 '14 at 16:20

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.