Re: Can someone give me an example of this type of problem?



Nathan Gilbert <nathan.gilbert@xxxxxxxxx> wrote:
> What is an example of a problem that is NP-Hard, but not in NP?

> I have seen the definition of NP-Complete as a problem that is both NP-Hard
> and in NP and began wondering about problems that didn't fit this definition.

> Thanks in advance,
> Nathan
> --
> "The life of a repoman is always intense."

The problem of determining if a regular expression is not
universal (that it does not contain all strings over the
alphabet) is NP-Hard but is not known to be in NP. This
is a decidable problem, unlike the Halting problem, but
is apparently harder than any NP-complete problem.

Stephen
.