Register

Np-complete Problems

772 views
0 votes
0 votes
I know that NP-complete problems are the hardest NP problems and every NP problem can be reduced NP-Complete problems in polynomial time. Now, it is said that all NP problems can be solved in Non-deterministic polynomial time, so is it true that ALL NP-COMPLETE PROBLEMS CAN BE SOLVED IN NON-DETERMINISTIC POLYNOMIAL TIME ?
User Avatar

1 Answer

1 votes
1 votes

Yes. All NP problems (Including NP-Complete Problems, since they are a proper subset of NP problems, assuming the current scenario i.e. P !=NP) can be solved in Polynomial Time on a Non-Deterministic Turing Machine.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1.2k
views
1 answers
0 votes
rahul sharma 5 asked Apr 16, 2018
1,223 views
Np Hard Problems
Are NP-Hard problems Semi decidable or Decidable or not even semidecidable?I know NP class is decidable as there is polynomial time NTM.But in the following figure in cas...
User Avatar
924
views
0 answers
0 votes
commenter commenter asked Jun 14, 2019
924 views
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 proble...
User Avatar
370
views
0 answers
0 votes
commenter commenter asked Jun 13, 2019
370 views
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...
User Avatar
877
views
1 answers
0 votes
radha gogia asked Jul 20, 2015
877 views
Are all NP problems reducible to NPC ?
I am a bit confused in this logic according to me all NPC are NP so that means all NPC are reducible to NP but since NPC are NP-hard as well so I guess that is not possib...
User Avatar
Link Copied!