0
$\begingroup$

Intuitively if A can reduce to B, and B is NP-Hard, A might be NP Hard but maybe not. If there is a way to solve A that does not involve reducing to B, it might be faster.

How do I formally disprove this statement using a counter example or some well known algorithms, or using some other technique?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Let A be the empty language. It is trivially reducible to, say 3SAT: transform any input into the formula $a \land \lnot a$. But only the empty language is reducible to the empty language, thus A is not NP-hard.

If P = NP, then any nontrivial language is NP-hard, thus it will be really hard to find counterexamples where both A and its complement are nonempty.

Improve this answer
$\endgroup$
2
  • $\begingroup$ can you clarify what empty language is? Is this a SAT where all clauses contain only 𝑎 and ¬𝑎 ? $\endgroup$
    – ChaiTea
    Apr 18, 2020 at 5:57
  • $\begingroup$ In decision problems we are asked to determine if the input string is in the language. An empty language is the language containing no strings. $\endgroup$
    – Antti Röyskö
    Apr 18, 2020 at 6:33

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.