In comp.theory KP Bhat <kbhat@sta.samsung.com> wrote: > martin dowd wrote: >> Important examples of unsolvable problems include: >> -is a statement of predicate logic valid? >> -is a statement in the language of rings true in the theory of rings? >> -is a polynomial with integer coefficients have an integer root? >> The list goes on. >> >> NP hard means every problem is NP is no harder. NP complete means in >> addition the problem is in NP. >>
> Having said that, can someone come up with more problems that are > NP-Hard ---- BUT NOT ------ NP Complete? Dowd's list above is a good > starting point. My guess is that only a handful of problems fall into > this category.
> Is that correct?
> IMHO an overwhelming majority of NP-Hard problems are also NP-Complete.
A lot of the natural NP-hard problems are NP-complete, but there are whole bunch of problems that are NP-hard and not not known to be NP-complete. For example, the problem of determining if two regular expressions represent different languages is NP-hard, but it does not seem to be in NP. This problem is decidable, so it is not as hard as the problems listed above. There are a whole bunch of problems from automata theory like that. It is also easy to take any NP-complete problem and create a similar problem that does not seem to be in NP. For example, the problem of determing if an instance of 3-SAT is uniquely satisfiable is NP-hard but apparently not in NP.
