6 votes

Is every non-recursively-enumerable language RE-hard?

Partial answer here: I think it at least depends on the chosen reduction. For example, consider $H\in \mathsf{RE}$ the halting problem. Then $\overline{H}\notin \mathsf{RE}$, but there is no many-one ...
Nathaniel's user avatar
  • 15.6k
3 votes
Accepted

Prove "Vertex Cover OR Clique" is NP complete

You can easily reduce from clique as follows. First, notice that the clique problem remains NP-hard even if we restrict $k$ to lie in $3 \leq k \leq n$ (because outside this range the problem is ...
Tassle's user avatar
  • 2,522
2 votes

Invertability of Karp reductions

The Berman-Hartmanis isomorphism theorem [1, p.312] says that poly-time invertible reductions exist between any two paddable NP-complete languages: If two NP-complete languages $A$ and $B$ are ...
Neal Young's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible