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 NPHard, but not in NP?
> I have seen the definition of NPComplete as a problem that is both NPHard
> 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 NPHard but is not known to be in NP. This
is a decidable problem, unlike the Halting problem, but
is apparently harder than any NPcomplete problem.
Stephen
.
 FollowUps:
 Re: Can someone give me an example of this type of problem?
 From: Nathan Gilbert
 Re: Can someone give me an example of this type of problem?
 References:
 Can someone give me an example of this type of problem?
 From: Nathan Gilbert
 Can someone give me an example of this type of problem?
 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):
Relevant Pages
