New answers tagged

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 ...
chi's user avatar
  • 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.'s user avatar
  • 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 ...
gnasher729's user avatar
  • 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.'s user avatar
  • 156k

Top 50 recent answers are included