Re: NPhardness
 From: stephen@xxxxxxxxxx
 Date: Wed, 29 Nov 2006 15:29:36 +0000 (UTC)
sara <sarasara82@xxxxxxxxx> wrote:
Thanks a lot. I wonder how is the procedure for proving NP hardness of
problems which are NPhard but not in NP. Is it similar to NP
completeness proof (reduction from a known NPcomplete decision problem
to our decision problem)?
It is very similar to an NPcompleteness proof. To prove a problem
is NPcomplete you need to prove that it is NPhard [1] (reduce a known
NPhard problem to it) and that it is NP.
By the way, topposting is considered bad ettiquette in these forums.
It makes it hard to follow the conversations.
Stephen
[1] I know that there are some different definitions of NPhard floating
about, but this is the one I'm most familiar with
jpalecek@xxxxxx wrote:
Hello,
sara wrote:
Hi All,
I am looking for a proof for a sketchy proof of NP hardness of an
Optimization problem which is NP hard but not NPcomplete like minimum
traveling salesman problem.
An example of such problem would be eg. finding minimum formula for a
given boolean function. The proof is simple in this case (like in many
cases,
the "belongs to NP" is actually harder).
We'll solve SAT by finding the minimum reprezentation of BF.
1) Find a minimum reprezentation of BF
2) Take a minimum reprezentation of "false"
3) If the sizes differ, BF is satisfiable.
4) If the sizes are the same, test all assignments of variables in the
minimum reprezentation of F
(this is O(1), because the minimum reprezentation of false has a
constant
size, therefore, there can't be more than a fixed number of
variables 
for example, if false is (x & non x), and the "size" is number of
variable
occurences, there can't be more than 2 variables)
This problem is {Sigma^P}_2. Actually, we don't know whether it is or
isn't in NP, for example, if P=NP, it is in NP.
There are (recursive) problems, that are surely outside NTIME(n^k) for
any k
therefore outside NP, but only ones I know of are artificial problems
obtained
by diagonalization (the Nondeterministic time hierarchy theorem). The
Halting
Problem is not recursive (eg. it is outside NSPACE(f), NTIME(f),
DSPACE(f),
DTIME(f) for any f:N>N)
For NPhard problems, see Garey, Johnson: ... (the NPc bible, don't
recall
the title at the moment).
Regards
Jiri Palecek
.
 References:
 NPhardness
 From: sara
 Re: NPhardness
 From: jpalecek
 Re: NPhardness
 From: sara
 NPhardness
 Prev by Date: Re: How to explain this to someone (highschooler)?
 Next by Date: Re: Is it possible for a probability to be unknown?
 Previous by thread: Re: NPhardness
 Next by thread: Early 19th/20th Century Algebra Texts
 Index(es):
Relevant Pages
