# 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.

> 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
.

## Relevant Pages

• Re: NP-hardness
... completeness proof (reduction from a known NP-complete decision problem ... NP-hard problem to it) and that it is NP. ... Optimization problem which is NP hard but not NP-complete like minimum ... We'll solve SAT by finding the minimum reprezentation of BF. ...
(sci.math)
• Re: NP - Hard -- Approximation algos
... A NP-hard problem is a problem such that every problem in NP poly-time ... (NP-complete). ... route shorter than k for this graph!", ...
(sci.crypt)
• Re: NP-complete and NP-Hard?
... There are NP-hard problems that are not in NP, ... Yes, NP-complete ... the trivial languages. ...
(comp.theory)
• Re: NP-complete and NP-Hard?
... I though that NP-complete is the intersection of ... NP and NP-hard. ... Isn't this question equivalent to P ?= NP? ...
(comp.theory)
• Re: origin of instruction idioms. are they still justified?
... There is a formulation of the problem that is NP-hard, ... The optimal algorithm for this sort of problem is to start by assuming ... Then check if all fit, ...
(comp.arch)