The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Questions by commenter commenter
User commenter commenter
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User commenter commenter
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
0
votes
0
answers
1
Proving a problem as NPcomplete.
According to this article, A problem X can be proved to be NPcomplete if an already existing NPcomplete problem (say Y) can be polynomialtime 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 NPcomplete? PS: I have already asked this question in cs.stackexchange
asked
Jun 14, 2019
in
Theory of Computation

64
views
pnpnpcnph
theoryofcomputation
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
pnpnpcnph
theoryofcomputation
timecomplexity
50,737
questions
57,324
answers
198,408
comments
105,174
users