menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Questions by commenter commenter

0 votes
0 answers
1
Proving a problem as NP-complete.
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 ... have to be only one way to prove a problem is NP-complete? PS: I have already asked this question in cs.stackexchange
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
2
Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?
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
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...