# Re: NP-hardness

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

Stephen

[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:

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

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 NP-hard problems, see Garey, Johnson: ... (the NP-c bible, don't

recall

the title at the moment).

Regards

Jiri Palecek

.

**References**:**NP-hardness***From:*sara

**Re: NP-hardness***From:*jpalecek

**Re: NP-hardness***From:*sara

- 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: NP-hardness** - Next by thread:
**Early 19th/20th Century Algebra Texts** - Index(es):