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

*From*: stephen@xxxxxxxxxx*Date*: Tue, 15 Nov 2005 18:46:48 +0000 (UTC)

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

.

**Follow-Ups**:**Re: Can someone give me an example of this type of problem?***From:*Nathan Gilbert

**References**:**Can someone give me an example of this type of problem?***From:*Nathan Gilbert

- Prev by Date:
**Re: Can someone give me an example of this type of problem?** - Next by Date:
**Re: Is P=NP? Thought process approach.** - Previous by thread:
**Re: Can someone give me an example of this type of problem?** - Next by thread:
**Re: Can someone give me an example of this type of problem?** - Index(es):