1,151 views
0 votes
0 votes

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?

1 Answer

1 votes
1 votes

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/

Related questions

0 votes
0 votes
2 answers
2
luc_Bloodstone asked Sep 22, 2019
668 views
I am having difficulty in understanding np and np-hard topic in algorithms. If someone can provide some good source to learn about it in easy manner it would be a real he...