New answers tagged reductions
0
votes
Accepted
Can an unreocognizable language be Turing-reducible to a recognizable language?
Any set $A$ Turing-reduces to its complement $A^c$.
Hence, the non-recognizable set $K^c$ Turing-reduces to the recognizable set $K=(K^c)^c$, where $K$ is the Kleene set (or, if you prefer, your ...
- 14.4k
0
votes
NP completeness of closest vector problem
There is a mismatch in terminology in your question. The problem you specify is known as the shortest vector problem (SVP). You called it the closest vector problem (CVP), but the CVP is something ...
D.W.♦
- 156k
0
votes
Reducing euclidean TSP of smaller size to euclidean TSP of bigger size
Here's an idea that doesn't work: Assume K = N-1. Take any node X and create another node X' at a distance epsilon from X, and calculate all the distances to X', then solve the N problem. If that ...
- 28.3k
0
votes
Reductions to perfect matching
This is trivially possible.
Solve the system $\mathcal{C}$ of linear equations, using Gaussian elimination.
If there is no solution to the system of linear equations, output a graph $\mathcal{G_C}$ ...
D.W.♦
- 156k
Top 50 recent answers are included