Log In

Questions by commenter commenter

0 votes
0 answers
According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs to be NP. Now my question is: Do we also need to prove that ... does this reduction have to be only one way to prove a problem is NP-complete? PS: I have already asked this question in cs.stackexchange
asked Jun 14, 2019 in Theory of Computation 231 views
0 votes
0 answers
I know that all NP problems can be reduced to Boolean Satisfiability SAT problem. But my question is whether SAT problem can be reduced to other NP complete problems like travelling salesperson problem TSP, 0/1 knapsack problem. In short are the reductions in NPC problems two ways?
asked Jun 13, 2019 in Theory of Computation 109 views