1 votes 1 votes Where does NP hard / NP complete problems fits in the Chomsky hierarchy ? Is there any relation of Np hard problems with RE languages? Theory of Computation theory-of-computation grammar + – rahul sharma 5 asked Nov 20, 2017 rahul sharma 5 1.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes NP-hard problems are at least as hard as the hardest problems in NP but there's no upper limit on how hard they themselves can be. There are NP-hard problems that are: In NP(take any NP-complete problem as an example) Not in NP but in R( problems in R that are not in NP ) Not in NP and not R(eg. the halting problem) Not even in RE (eg. the complement of the halting problem) Putting this all together, you can visualize these classes in a Venn diagram like so: (If P=NP, then the innermost region would be a single circle representing P=NP=NP-complete) SOURCE:https://cs.stackexchange.com/a/90677 Parth Shah answered Sep 1, 2018 Parth Shah comment Share Follow See all 0 reply Please log in or register to add a comment.
–1 votes –1 votes NP hard problems belongs to RE languages because no algorithm exist for finding the solution of this even in unlimited time so these are undecidable problem therefore RE. Divyendi answered Sep 1, 2018 Divyendi comment Share Follow See all 0 reply Please log in or register to add a comment.
