# NP hard/complete

I have never been very clear on this concept. Please help:

At the end of the day, we should want to identify useful problems for which we don't have polynomial solution so far and only have exponential solutions.We want to keep finding if we can find a polynomial solution to these problems and the use of reductions is only to be able to identify new only exponential solvable problems with help of existing known exponential problems.??

Why is concept of determinism and non determinism brought into this whole concept of exponential and polynomial solvable problems?? How is this notion useful?

What do we call the problems for which we have only exponential solution so far, but we haven't been able to find reduction to a known NP - hard/complete problems..??

Thanks,

-

I would say that the concept of 'nondeterminism' is one of the great red herrings in the discussion of NP-complete problems. To my mind it's much better to think of a problem's being in NP as a criterion for confirming solutions; 'if we're given a hypothetical solution instance for a problem, can we verify it in polynomial time?'. Seen this way, a lot of problems in NP become a lot clearer: for instance, Satisfiability (of a boolean expression) is verified just by plugging in the purported assignment to all the variables of the expression and confirming that the result is true; the Traveling Salesman Problem can be verified by confirming that a proposed route gets to all cities, doesn't go to any city more than once, and has total length under the requisite bound; etc. All of these obviously take polynomial time to confirm. 'Exponential solvability' is really a red-herring; it happens that there's an obvious exponential-time algorithm for NP-complete problems (use our polynomial-time checking algorithm on each of the exponentially-many possible solution instances), but the exponentiality isn't really at the heart of these problems; it's just an expression of the size of the search space. Seen this way, the P vs. NP question becomes 'if we can efficiently confirm a solution, can we efficiently find a solution?' - but this has nothing to do with exponential-time problems in and of itself.

-
It seems that we wrote basically the same points at the same time... – JDH May 20 '11 at 17:40
It's a knack. :-) (And all the more interesting to me because I know the sentiment on how to view NP isn't entirely universal; it's just my favorite characterization, so it's good to know that someone else agrees with that perspective.) – Steven Stadnicki May 20 '11 at 18:09

The NP problems are those for which we have a (deterministic) algorithm to verify that a proposed solution really is a solution. Thus, the question of whether a given logical expresion is satisifiable is NP, since we can correctly verify whether a proposed truth assignment is satisfying or not in polynomial time. The questions of whether a given salesman travel map has a route visiting every city within a fixed travel budget is NP, because we can verify whether any proposed route fits the requirements in polynomial time. The difficult part of an NP problem, rather, is to come up with the proposed solution, to come up with the satisfying truth assignment or the efficient travel route.

These NP problems are all exponential time solvable, because the silly algorithm of just trying out all the possible combinations in turn takes exponential time. Non-determinism comes into the picture because one can view the procedure of "guessing the right answer" and then verifying it as a nondeterministic algorithm. Thus, NP problems are those which have a non-deterministic polynomial time algorithm.

-

The: If $\text{P} \neq \text{NP}$ implies NP-Hard problems require exponential time algorithms is a common myth, which seems quite prevalent.

In fact, we have known NP-Hard problems which have sub-exponential algorithms! For instance see this here: http://hal.inria.fr/docs/00/47/66/86/PDF/cops_journal_2008_10_16.pdf

That said, there is a conjecture, called the Exponential Time Hypothesis which states that 3-SAT (and some of it's variants) cannot be solved in sub-exponential time.

Now you might wonder why does the above sub-exponential algorithm for an NP-Hard problem not falsify the Exponential Time Hypothesis, as we can ultimate form a reduction from 3-SAT?

The reason is that reductions are allowed to blow up the input polynomially. Say $A$ reduces to $B$ and $B$ has a $\theta(2^{\sqrt{n}})$ time algorithm. Now if the reduction makes the size of the input to $B$ as $n^2$ (it was $n$ for $A$), that still gives us a $\theta(2^n)$ time algorithm for $A$. So, even though $A$ never has sub-exponential time algorithms, we could still have it reduce to a problem which has sub-exponential time algorithms.

As to why we have non-determinism, I am guessing this was first started by Rabin and Scott in their papers about deterministic finite automaton and non-deterministic finite automaton.

Once Cook/Levin introduced the concept of NP-Completeness and Karp et al gave a seminal list of 21 natural problems which are NP-Complete, NP became a very important class.

I believe it was Edmonds who first characterized NP as 'problems with polynomial certificates'.

(Note: The above three paragraphs are from memory and I haven't verified them).

In fact, there are characterizations of NP which do not use non-determinism. The current hot topic has been the use of PCP Theorem to prove various NP-Hardness results for approximation versions of NP-Hard problems.

So, non-determinism is still part of the definition of NP and is historically important, but the current status is that it is not mandatory.

-
Can you point out where in the Cops & Robbers paper they prove a sub-exponential algorithm for an NP-hard problem? My reading of the abstract and the list of open problems at the end is that the general problem is NP-hard but certain classes of instances are not. – Peter Taylor May 20 '11 at 22:38
@Peter: The paper proves that computing $c_1(G)$ is NP-Hard (section 2, page 4) and claims a sub-exponential time algorithm for it (section 1, page 3). – Aryabhata May 20 '11 at 23:29
Thanks. The big thing I was missing is that the sub-exponential algorithm isn't a new result, so they don't mention it in the abstract. – Peter Taylor May 21 '11 at 7:55