Np-complete Problems

Harsh Kumar asked Mar 20, 2018

759 views

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 ?

Theory of Computation
p-np-npc-nph
theory-of-computation

+ –

Harsh Kumar asked Mar 20, 2018

Harsh Kumar

759 views

See all

0 Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

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.

Deepak Poonia answered Mar 20, 2018

Deepak Poonia

See all

0 Please log in or register to add a comment.

Voting & Accepting an answer helps improve the community

← Previous Next →

← Previous in category Next in category →

Related questions

0 votes

1 answer

rahul sharma 5 asked Apr 16, 2018

1,178 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 case there are some NP hard problems that are lying outside of NP.Problems which are NP-hard but not NPC.Can these also be solved in polynomial time by NTM?

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...

rahul sharma 5

1.2k views

rahul sharma 5 asked Apr 16, 2018

Theory of Computation
p-np-npc-nph
theory-of-computation

+ –

0 votes

0 answers

commenter commenter asked Jun 14, 2019

864 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 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 proble...

commenter commenter

864 views

commenter commenter asked Jun 14, 2019

Theory of Computation
p-np-npc-nph
theory-of-computation

+ –

0 votes

0 answers

commenter commenter asked Jun 13, 2019

358 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...

commenter commenter

358 views

commenter commenter asked Jun 13, 2019

Theory of Computation
p-np-npc-nph
theory-of-computation
time-complexity

+ –

0 votes

1 answer

radha gogia asked Jul 20, 2015

845 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 possible since if x is reduced to y that means y must be harder than or equal ... it that all NP are reducible to NPC or all NPC are reducible to NP , I am a bit confused in this , so please help.

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...

radha gogia

845 views

radha gogia asked Jul 20, 2015

Algorithms
algorithms
p-np-npc-nph

+ –

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

0 reply

Please log in or register to add a comment.

Please log in or register to answer this question.

1 Answer

0 reply

Please log in or register to add a comment.

Related questions

0

0