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


Relevant Pages

  • Re: Can someone give me an example of this type of problem?
    ... > 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. ... is apparently harder than any NP-complete problem. ...
  • 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!", ...
  • Re: NP-hardness
    ... I am looking for a proof for a sketchy proof of NP hardness of an ... We'll solve SAT by finding the minimum reprezentation of BF. ... If the sizes differ, ... For NP-hard problems, see Garey, Johnson: ...
  • Re: NP-complete and NP-Hard?
    ... There are NP-hard problems that are not in NP, ... Yes, NP-complete ... the trivial languages. ...
  • 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? ...