Questions by commenter commenter - GATE Overflow

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

asked Jun 14, 2019 in Theory of Computation | 64 views

0 votes

0 answers

2

Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?

asked Jun 13, 2019 in Theory of Computation | 49 views

50,737 questions

57,324 answers

198,408 comments

105,174 users