The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
184 views

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?

asked in Theory of Computation by Boss (26.5k points) | 184 views
+1
NPC is decidable

$NP Hard\preceq NPC$

So, NP Hard is atmost as hard as NPC

NP hard decidable

As, Undecidable is superset of decidable

NP Hard cannot be undecidable

1 Answer

+1 vote

Problems which are NP-hard but not NPC.Can these also be solved in polynomial time by NTM?

Of course "NO", because then these problems will be in NP and hence NPC. 

https://gatecse.in/p-np-np-complete-np-hard/

answered by Veteran (377k points)
0
ok, then some NP hard problem cannot be reduced to NPC or NP?
then what those NP Hard mean?
why term NP came before those NP Hard problem?
0
yes, some NP-hard problems cannot be reduced to a NP problem or otherwise NP-hard = NPC. i.e., if you reduce any NP-hard problem to a NP problem, that problem now becomes NPC. It is all given in the definitions of NP,NPC and NP-hard - yes some by-heart required here and then you can think logically.

Related questions



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

46,769 questions
51,220 answers
176,475 comments
66,581 users