Skip to main content

New answers tagged

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.7k
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
0 votes

Polynomial-Time Solvability Through NP-Completeness Reductions

Yes, that would be the case, and here is my argument. Suppose there is a polynomial time reduction problem $A$ to problem $B$. So basically, we have a mapping function $f$ that converts any input of ...
codeR's user avatar
  • 706
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
0 votes

Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement

The short answer to your question is no. There is no such a reduction. Your question is actually can be answered using theorem which is stated here: Prove that a language does not many one reduce to ...
Ali Dastjerdi's user avatar

Top 50 recent answers are included