Question

A polynomial time algorithm for an np-hard problem does not imply every problem in np has a polynomial time algorithm. Justify

Answer 1

To show a problem is NP complete, you need to:

Show it is in NP

In other words, given some information C, you can create a polynomial time algorithm V that will verify for every possible input X whether X is in your domain or not.

Example

Prove that the problem of vertex covers (that is, for some graph G, does it have a vertex cover set of size k such that every edge in G has at least one vertex in the cover set?) is in NP:

our input X is some graph G and some number k (this is from the problem definition)

Take our information C to be "any possible subset of vertices in graph G of size k"

Then we can write an algorithm V that, given G, k and C, will return whether that set of vertices is a vertex cover for G or not, in polynomial time.

Then for every graph G, if there exists some "possible subset of vertices in G of size k" which is a vertex cover, then G is in NP.

Prove it is NP Hard

This involves getting a known NP-complete problem like SAT, the set of boolean expressions in the form:

(A or B or C) and (D or E or F) and ...

where the expression is satisfiable, that is there exists some setting for these booleans, which makes the expression true.

Then reduce the NP-complete problem to your problem in polynomial time.

That is, given some input X for SAT (or whatever NP-complete problem you are using), create some input Y for your problem, such that X is in SAT if and only if Y is in your problem. The function f : X -> Y must run in polynomial time.

Footnote: In step 2 (Prove it is NP-hard), reducing another NP-hard (not necessarily NP-complete) problem to the current problem will do, since NP-complete problems are a subset of NP-hard problems (that are also in NP).

Answer 2

Question

A polynomial time algorithm for an np-hard problem does not imply every problem in np has a polynomial time algorithm. Justify

Answer

specifically is that if you have an algorithm [math]A_1 [/math]to solve a NP-Hard problem, you can build, for any NP problem, an algorithm [math]A_2[/math] which runs in the "same time" as [math]A_1[/math] (the complexities of the two algorithms will have at most a polynomial-time difference).