Non-determinism, Polynomial time problems and NP-complete

[jaydee]

I've been researching these for awhile for a high school physics project, but still don't have a clear idea what they mean. From what I've learned thus far:

A P problem is classified as one where the number of steps are bounded by some power of the problems size. (Would this be like solving for 2^x, where the difficulty is bounded by how large x is?)

An NP problem is classified as one where the number of steps are bounded by some power of the problems size by a non-deterministic Turing machine. [What is a (or an example of) a non-deterministic Turing machine?]

NP-hard is classified as a problem that has an algorithmic solution that can be used to solve any other NP-problem. (I really have no idea what this is suppose to mean.)

NP-complete is both NP and NP-hard.

I've gathered that the Hamiltonian path (traveling salesmen) problem is NP-complete. (Because the difficulty increases exponentially with the number of cities?)

Theoretically, quantum and DNA computers would solve this type of problem in a vastly more efficient time frame then a convential one.

One final question, is how would a 64-bit computer (and OS) compare to a 32-bit system in solving these types of problems?

 

[m0ti]

A P problem is one that for which exists a Turing machine that solves it (accepts the related language) in polynomial time. More restrictively, so it'll be easier to understand, if for a given problem of length x, there exists a deterministic algorithm (as in first do this, then do that, ...), and a polynomial p, such that the machine solves the problem in time p(x).

An NP problem is for a non-deterministic machine. For example, for TSP (travelling salesman problem):

Select a random permutation of cities to visit (takes O(n) time).
Check if the path defined is below the specified cost (O(n) time).

Note that there are n! different permutations, which gives us the width of the tree (the number of possible computation paths). If a graph and cost belong to TSP, then the above non-deterministic machine will find it (where the selection is the non-deterministic part). Actually Hamiltonian path is a different problem than TSP, but there is a simple reduction from HP to TSP.

NP-Hard problems are problems which are at least as hard as all the problems in NP. NP-Complete problems are NP-Hard problem in NP. Cook's theorem provides for showing that the satisfiable CNF clause problem (SAT) is NP-Hard (and NP-Complete). After that reductions from SAT to other problems and from those to others can be used to show that others are also NP-Hard or NP-Complete (for example 3-SAT, 3-COL, clique, etc).

NP problems can always be solved in determinstic exponential time. There are exponential problems which aren't in NP.

Quantum computers are effectively non-deterministic machines. The same can be said for DNA computation, where strand length can be used to simulate branchings.

As for 64 bit vs. 32 bit, it can speed up computations somewhat, but unless you start doing the calculations in parallel, it won't be turning the majority of NP-Complete problems into computationally feasible ones for large inputs any time soon.

 

[jaydee]

Thanks for the quick response. A few more questions.



<< Note that there are n! different permutations, which gives us the width of the tree (the number of possible computation paths). If a graph and cost belong to TSP, then the above non-deterministic machine will find it (where the selection is the non-deterministic part). >>


By cost you mean the total distance traveled correct? And by graph, you mean you have the coordinates of all the points?



<< Actually Hamiltonian path is a different problem than TSP, but there is a simple reduction from HP to TSP. >>


So TSP is derived from (and a type of) Hamiltonian path problem?



<< NP-Hard problems are problems which are at least as hard as all the problems in NP. NP-Complete problems are NP-Hard problem in NP. >>


Could you give me an example of an NP, and NP-Hard problem?
I think I understand NP-complete now, thanks.



<< Cook's theorem provides for showing that the satisfiable CNF clause problem (SAT) is NP-Hard (and NP-Complete). After that reductions from SAT to other problems and from those to others can be used to show that others are also NP-Hard or NP-Complete (for example 3-SAT, 3-COL, clique, etc). >>


This just about lost me.

Thanks for the time, I really do appreciate it.

 

[m0ti]

Ok, first off any problem in P is also a problem in NP. That's because a deterministic Turing machine is identical to a non-deterministic one which only has one choice from which to select at any stage.

TSP is defined as all the (G,w,k)'s such that G is a fully connected graph, w is the weights of its edges, such that there exists a Hamiltonian circle with weight less than or equal to k.

Hamiltonian circle is defined as all the (G)'s such that G is a graph, and it contains a Hamiltonian circle.

We will now show a reduction from HC to TSP:

f(G) = (G',w,k)

where: G' has the same vertices V as in G. G' is fully connected.

w(e') = 1 if e' is an edge in G, else 2.

k = |V| (the number of vertices).

We see that if there is a solution to G for HC then there exists an HC in G' with weight |V| (in other words, the group belongs to TSP). If there isn't, all the HC's in G' have a weight of at least |V| + 1 (and the group doesn't belong in TSP).

Therefore, TSP is NP-Hard if HC is NP-Hard (which it is, based on other reductions). Since TSP is also in NP, TSP is therefore NP-Complete.

Similarly we can do a transform from HP to HC (I'll show it less formally):

In standard HP we want to know if a Hamiltonian path exists from u to v in graph G.

What we do, is add another vertex (x) to the graph and connect it to both u and v, and to nobody else. If in the new graph there is a hamiltonian circle than the section u-x-v must appear in it. Therefore, if we were to start from u we can go through all of the vertices in the graph other than v and x, before arriving at v and finally x. therefore, in the previous graph we had a hamiltonian path. If there wasn't a Hamiltonian Path in the first graph, then there can't be an HC in the new one, since it would have to include x (as part of u-x-v and there would then be an HP, which negates our assumption).

Basically, what we're doing here is doing reductions from NP-Hard problems to other problems to show that these new problems are also NP-Hard. However, there must be some starting point to all this (chicken and the egg). There must be some problem which can be shown to be NP-Hard without having done a reduction from another NP-Hard problem. The problem that we want should be NP-Complete, in fact, since if it isn't in NP, it will be useless for discovering NP-Complete problems. Cook's theorem (and proof) shows that SAT (logically satisfiable clauses in Conjunctive Normal Form) are NP-Complete. Then, it is simple to create reductions from SAT to other problems, and from those problems to others, resulting in more and more NP-Complete (or Hard) problems.

 

[Carceri]

<< Quantum computers are effectively non-deterministic machines. >>


There are elements of non-determinism in a quantum computer, but not the same as we think of regarding a non-deterministic turing machine. That is also supported by the fact that a quantum computer can't solve NP-Complete problems in polynomial time.

 

[Modus]

My cat's breath smells like cat food.

Modus

 

[ErikaSwift2000]

Actually it is unknown whether Quantum Polynomial is equivalent to non-deterministic polynomial time. Factoring and Discrete Log are in Quantum Polynomial time -- though neither are known (or believed to be) NP-hard problems.

Now, P and NP are technically speaking just sets (containing languages -- which can also be thought of as sets).

A language is in P if membership in the language can be decided using a number of steps that's polynomial in the SIZE of the input on a deterministic turing machine. For example, the language consisting of all bit strings with an even number of 1's -- that's in P.

A language is in NP if membership in the language can be decided using a number of steps that's polynomial in the SIZE of the input on a non-deterministic turing machine.

An alternate characterization of NP is languages such that for any element in the language, there exists a short proof (also called a witness) that the element is in the language. The short proof should be such that it can be verified in polynomial time on a deterministic machine.

A Turing machine is essentially equivalent to a modern computer (technically they are polynomially equivalent).

For example consider the language of Composite numbers -- a short proof can consist of the factorization of the number. In Hamiltonian path, the short proof consists of the actual path -- it can be verified easily on a Turing Machine.

You might want to check out Cormen, Leiserson and Rivest's "Introduction to Algorithms" for a good treatise on the subject (which is not overly technical).

Hope this helps.

Erika. 🙂

 

[jaydee]

Thanks a lot for the help guys. I'm going to carefully exam this stuff with my Physics teacher (EE major), and my Calculus teacher (CS major) and see if we can figure it out. I'll probably have a few more questions by the end of the week. Thanks again, it's been a great help so far.

 

[Carceri]

<< Actually it is unknown whether Quantum Polynomial is equivalent to non-deterministic polynomial time. Factoring and Discrete Log are in Quantum Polynomial time -- though neither are known (or believed to be) NP-hard problems. >>


Ok, I was not being very specific. Here are some results from quantum complexity classes (without proofs)

PSPACE is the class of decision problems that can be solved by a turing machine using only polynomial space, but with no limit on the computation time.
BQP is the class of decision problems that can be solved by a quantum computer with bounded probability using a polynomial amount of quantum gates.

It is in fact possible to establish some relations between those two classes. It is possible to show that BQP is contained in PSPACE and it's also clear that BPP is in BQP (BPP is just BQP without a quantum computer). ("is in" could also mean that the classes are equal). Thus we have:

BPP in BQP in PSPACE

So if we could prove that BBP is different from BQP it would mean that quantum computers are more powerful than regular computers. But it would also imply that BPP is different fom PSPACE (which is still unknown - so proving that quantum computers are more powerful than regular computers would also yield another very interesting result in classical complexity theory)

On a different note one can prove that using black box only computations on a quantum computer one can at best achieve a polynomial speedup over a classical algorithm. There are some indications that this result can be generalized to a greater class of problems (perhaps all NP-Complete problems), but it has not been proven yet. What it SEEMS to indicate is that NP-Complete problems can only get a polynomial speedup using a quantum computer. We have already proven that factorization can get an exponential speedup on a quantum computer so factorization is not NP-Complete. There are also strong evidence that factorization is somewhere between P and NP-Complete.

The last section is just more or less guesswork - no one knows for sure today.