Re: NP-hardness

sara <sarasara82@xxxxxxxxx> wrote:
Thanks a lot. I wonder how is the procedure for proving NP hardness of
problems which are NP-hard but not in NP. Is it similar to NP
completeness proof (reduction from a known NP-complete decision problem
to our decision problem)?

It is very similar to an NP-completeness proof. To prove a problem
is NP-complete you need to prove that it is NP-hard [1] (reduce a known
NP-hard problem to it) and that it is NP.

By the way, top-posting is considered bad ettiquette in these forums.
It makes it hard to follow the conversations.


[1] I know that there are some different definitions of NP-hard floating
about, but this is the one I'm most familiar with

jpalecek@xxxxxx wrote:

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 NP-complete 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
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
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
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
by diagonalization (the Nondeterministic time hierarchy theorem). The
Problem is not recursive (eg. it is outside NSPACE(f), NTIME(f),
DTIME(f) for any f:N->N)

For NP-hard problems, see Garey, Johnson: ... (the NP-c bible, don't
the title at the moment).

Jiri Palecek