NP hard/complete

Question

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,

Answer 1

There's nothing obvious about determinism and non-determinism that leads to this. It's a bit technical.

A deterministic automaton corresponds to what we can actually build, either in hardware or in software.

A non-deterministic automaton tries all possible solutions, but to be in polynomial time it has to be able to verify a possible solution in polynomial time. If you enough of the theory, you'll recognize that an NA is equivalent to a DA with an oracle that mysteriously gives a solution, so an NA can solve something in polynomial time if a DA can verify a proposed solution in polynomial time. A nondeterministic automaton is equivalent to a deterministic automaton that tries all possible combinations, and the set of all possible combinations has exponentially more members than the set of things being combined, so if a NA can do something in polynomial time a DA can certainly do it in exponential.

NP is the set of decision problems such that a DA (hence a real computer) can verify a solution in polynomial time. If we can't verify a proposed solution in polynomial time, we certainly aren't going to be able to generate one, so NP is essentially the set of decision problems that might have real-life polynomial-time solutions.

The Traveling Salesman Problem, as usually given, isn't in NP because it's not clear how to verify that a given route is the cheapest in polynomial time. However, a variant of the TSP in which the question is whether there's a solution with a cost under X is in NP, since it's easily verifiable, and if we can solve that problem we can determine the cheapest route easily. Therefore, the TSP as usually stated is NP-hard, meaning that it's as hard to solve as an NP-complete problem.

There are problems that don't have known polynomial solutions for an NA, and problems we know aren't in NP. Those problems are usually categorized by further complexity classes (PSpace problems, for example, can be solved in polynomial space, but possibly only exponential time), or listed as undecidable. I don't know of any terms for a problem, say, that is PSpace but is not known to be in NP.

Answer 2

NP takes it's name from the fact that it can be solved in polynomial time by non-deterministic Turing machine. The trick is that non-deterministic in that case means, as if it can magically evaluate all branches in parallel. It's a theoretical model, you should not attempt to compare it with real life computers. In fact it has much more to do with area of mathematics know as formal languages and computability theory.

NDTM can be "reduced" to deterministic Turing machine, but in exponential time. That's why there are no polynomial solutions for NP-complete problems on computers, which (as you correctly noted) are deterministic.

Answer 3

The concept of deterministic versus non-deterministic comes into play from the way these problems are being studied on Turing Machines.

Conceptually, a Turing Machine can solve any Turing complete problem through one of two methods:

1. Each action is performed sequentially with no branching when a decision is made, i.e. deterministic in that you can follow the exact path of execution yourself.
2. Each action is performed sequentially but a branch occurs when ever a decision is made so that each branch can be explored, i.e. a non-deterministic Turing machine.

Thus, on a non-deterministic machine, if the algorithm can find a solution, you know that a solution exists that was found in polynomial time, but you don know know which execution branch was used in order to find that solution. Things get interesting though because a Turing machine can simulate a non-deterministic Turing machine but in order to do so it must calculate each pathway through the code and this is where the exponential nature of NP problems.

Turing machines are used for this sort of study due to their simple nature which makes understanding them at a mathematical level much easier when you are concerned about the core mathematics of the problem without having to worry about the overhead that might be involved with using different types of machines.

In regards to a problem for which we have a a exponential solution on a deterministic Turing machine but no reduction to a known problem, it would to EXPTIME.