Could someone explain the point of NP problems in computer science?

[Rainsford]

In my algorithms class, we just finished learning about NP problems and NP complete problems, and I have to say I'm a little confused. The idea is an interesting one, but as far as I can see, we would have to have a very radical shift in processor design to have non-deterministic computers. And without those, the whole idea of NP problems doesn't matter because we have no way of making the correct guess required to even do those kind of problems.

Perhaps I don't really understand NP problems, my teacher was pretty bad. If I'm missing something, I'd appreciate it if someone cleared this up for me.

 

[Matthias99]

Alright, a problem right up my alley.

Maybe it would be helpful if we started by discussing the set P and then seeing how the set NP relates to it.

Problems (or, pretty much equivalently, the algorithms used to solve the problems) in computer science are usually analyzed in what's known as "Big-O" notation -- that is, a way of expressing how many low-level operations are required to solve a problem of input size N.

For example, a merge sort is of algorithmic complexity O(N * log2(N)) -- that is, to sort N items using a merge sort, it will require at most (N * log2(N)) operations.

A problem that can be solved in time polynomial with respect to N (that is, it requires less than or equal to N^X operations for some fixed number X) is in the set P (P standing for "Polynomial"). One of the thorniest unsolved problems in computer science has to do with a subset of the problems that are *not* in this set.

A problem which can definitely be solved in exponential time (that is, requiring less than or equal to X^N operations for some fixed number X > 1), but which does not seem to be solvable in polynomial time, is in the set NP (for "non-polynomial"). These are also sometimes called "non-deterministic" problems, for reasons that I won't go into here.

Many very interesting problems are in the set NP. This includes a great deal of search algorithms, game theory problems, and certain logical analysis alogorithms. The simplest example I can think of to compare a P against an NP problem is 2-SAT and 3-SAT. These are problems for analyzing a description of a logic circuit.

In a SAT probem, you are given a description of a binary logical circuit using AND, OR, and NOT gates, and you have to determine if there is a way for the circuit to output TRUE. If it can, it is said to be "satisfiable" (hence why the problem is called SAT).

In 2-SAT, each "gate" can only have two inputs. One example of such a problem might be: (A AND B) OR (B AND C). This circuit can be made to output TRUE if A and B are true, or B and C are true (or if A, B, and C are all true). I won't try to prove this here, but you can write an algorithm that will take such a description as an input and tell you if the circuit is satisfiable in polynomial time (it's O(N^4), I believe).

In 3-SAT, each "gate" has *three* inputs. You might have: (A AND B AND C) AND (B OR C OR A) AND (C AND D AND NOT(A)). This circuit is *not* satifiable, as A would have to be both TRUE and FALSE at the same time. However, as far as anyone can tell, you *cannot* write an algorithm that will solve this program in polynomial time. The best algorithm that exists to solve this problem takes O(3^N) time. Thus, 3-SAT is an NP problem.

Of the NP problems, there are a subset which can all be proven to be the "same" problem. That is, you can convert from an instance of one problem to another in polynomial time. These are called the "NP-Complete" problems (3-SAT is one, for example). Others include finding a minimum spanning tree of an arbitrary graph, and solving a minesweeper board (no, really!). There are also "NP-Hard" problems -- these appear to be as hard as the NP-Complete ones, but they aren't the "same" -- it would take more than polynomial time to convert between them. These problems have been studied intently for the last 50 years or so. However, so far nobody has found a way to solve them in polynomial time -- but nobody has proven yet that you *can't* solve them in polynomial time, either. This is probably the biggest unanswered question in theoretical computer science: does P = NP?

If P=NP (or, more specifically, if the NP-Complete problems are actually in set P), then all of these problems (which are now currently impossibly hard to solve when N starts getting even moderately large) could be solved very rapidly in real time. This would likely take care of all computational needs for the forseeable future, as the NP-Complete problems are basically the only things that computers can't do in a very short amount of time already (except for certain mathematical things, such as factoring really large numbers, which is NP-Hard but not NP-Complete).

If P != NP, then these problems will never be able to be solved in a reasonable amount of time without a quantum computer (which operates in a non-deterministic way in order to perform Q^2 operations per time step, where Q is the number of Q-bits in the computer).

The reason anybody *cares* about this is that many of the NP-Complete problems are things that *have* to be solved (for instance, N-SAT problems are used in circuit simulation and verification, which -- trust me -- takes a damn long time to run for large circuits), and so an enormous amount of computer time is spent solving them now. It would be nice to at least know whether or not it's possible to solve them more quickly.

 

[Rainsford]

Originally posted by: Matthias99
Alright, a problem right up my alley.
<SNIP>

Well I kind of see what you mean, and a lot of that we learned in my class. But I still don't understand this whole idea of solving the problems using theoretical non-deterministic means. Computers are deterministic by their very design, and while I see that a lot of those problems are useful to know how to solve (believe me, I'm a Computer Engineering student and I've done some pretty big circuit simulations, and they are sloooow), I don't see the interest in figuring out how to solve them assuming some non-deterministic method is found.

Example. In class we are doing a tree searching algorithm that did some other things and our teacher was asking us to figure out the time it would take assuming we made the correct guess at each branching point. This non-deterministic approach to solving the problem seems moot to me since there is no way to make the correct guess at each point without taking a whole lot of other steps. Computers aren't too good at guessing.

I suppose the field is interesting if you can solve an NP problem in polynomial time, but as far as analyzing them using some magic non-deterministic computer, I don't see the point.

 

[Matthias99]

Originally posted by: Rainsford

Computers are deterministic by their very design, and while I see that a lot of those problems are useful to know how to solve, I don't see the interest in figuring out how to solve them assuming some non-deterministic method is found.

This, I think, is why you're a Comp Engin major rather than a true CS geek.

Example. In class we are doing a tree searching algorithm that did some other things and our teacher was asking us to figure out the time it would take assuming we made the correct guess at each branching point. This non-deterministic approach to solving the problem seems moot to me since there is no way to make the correct guess at each point without taking a whole lot of other steps. Computers aren't too good at guessing.

This is why the problems are often called "Non-Deterministic" -- you can check an individual solution in polynomial time, but there are an exponential number of possible solutions. This behavior is not terribly helpful when you're working with deterministic computers (ie, the ones we have today), as you noted. However, it's sort of an interesting phenomenon on its own!

I suppose the field is interesting if you can solve an NP problem in polynomial time, but as far as analyzing them using some magic non-deterministic computer, I don't see the point.

The field is interesting because we don't *know* if you can solve an NP problem in polynomial time. That's why people study them so much -- the answer to this question may say an awful lot about the limits of computation in our universe. This is actually a "why" question that there might be answer to -- why is 2-SAT in P but 3-SAT (which is a very similar problem) in NP?

If someone solves this question in the negative -- that is, proves that P != NP -- then I'm sure this subject will be relegated to some dusty academic books that nobody ever reads except in grad school CS courses.

 

[rjain]

Actually, non-deterministic evaluation is pretty simple, but has nothing directly to do with NP problems. I don't see how we're using non-deterministic means to solve the problems "in theory". Such algorithms are used, but I don't know if they're restricted to NP problems.

Quantum computers operate perfectly deterministically. They're just implicitly parallel. By the logic you guys are using, any multiprocessor system is non-deterministic (yeah, the performance characteristics are ).

Matthias99: You're assuming that computation in the universe (quantum mechanics, particularly decoherence) is algorithmic, which seems highly unlikely.

Edit: to expand on why, it's probably the only way that the 2nd law of Thermo can be maintained in the presence of black holes. It looks like black holes destroy information, which means that they also destroy entropy. Entropy can be created by having decoherence occur randomly, balancing out the loss from black hole absorption. Whether the two phenomena are directly connected or whether the 2nd law is merely an "engineering" phenomenon (in the same way that Kepler's laws are an "engineering" phenomenon). This makes sense since the real root of Thermodynamics is statistics, and statistics aren't a guarantee.

 

[Rainsford]

Originally posted by: rjain
Actually, non-deterministic evaluation is pretty simple, but has nothing directly to do with NP problems. I don't see how we're using non-deterministic means to solve the problems "in theory". Such algorithms are used, but I don't know if they're restricted to NP problems.

I'm not sure I follow. As I understand it, a non-deterministic algorithm is impossible, or at least impracticle. Sure, you could guess and check, guess and check, but that would take far longer than using a deterministic algorithm unless, as was stated in my class, you had a means to make the correct guess every time you had to guess and then the checking would run in polynomial time. Or of course you could try every solution in parallel, but that isn't really possible on any processor I've ever heard of.

Quantum computers operate perfectly deterministically. They're just implicitly parallel. By the logic you guys are using, any multiprocessor system is non-deterministic (yeah, the performance characteristics are ).

I don't know about that. A multi-processor system can run instructions in parallel, but only to a finite point. Maybe I just don't have a good grasp of the definition of non-deterministic.

Matthias99: You're assuming that computation in the universe (quantum mechanics, particularly decoherence) is algorithmic, which seems highly unlikely.

Edit: to expand on why, it's probably the only way that the 2nd law of Thermo can be maintained in the presence of black holes. It looks like black holes destroy information, which means that they also destroy entropy. Entropy can be created by having decoherence occur randomly, balancing out the loss from black hole absorption. Whether the two phenomena are directly connected or whether the 2nd law is merely an "engineering" phenomenon (in the same way that Kepler's laws are an "engineering" phenomenon). This makes sense since the real root of Thermodynamics is statistics, and statistics aren't a guarantee.

 

[Matthias99]

Actually, non-deterministic evaluation is pretty simple, but has nothing directly to do with NP problems. I don't see how we're using non-deterministic means to solve the problems "in theory". Such algorithms are used, but I don't know if they're restricted to NP problems.

Another possible definition of an NP-Hard problem is one that can be solved in polynomial time non-deterministically (that is, if you know the answer in advance, you can verify its correctness in polynomial time). I believe that's what was being referred to here.

You're right that it's not really correct to call a quantum computer "non-deterministic"; it is, however, exponentially parallel in the number of Q-bits available for use. This means a quantum computer containing N Q-bits can solve one of these "non-deterministic" NP-Complete problems of size N in polynomial time (in theory!)

Matthias99: You're assuming that computation in the universe (quantum mechanics, particularly decoherence) is algorithmic, which seems highly unlikely.

Perhaps I should have said the limits of algorithmic computation in our universe. My knowledge of information theory stops when astrophysics starts creeping into it.

 

[rjain]

Originally posted by: Rainsford

I'm not sure I follow. As I understand it, a non-deterministic algorithm is impossible, or at least impracticle.

Non-deterministic algorithms are old hat. Late 60s or something. Any time there is a choice in your search, you randomly choose one option. If that one fails, you try the other choice.

I don't know about that. A multi-processor system can run instructions in parallel, but only to a finite point. Maybe I just don't have a good grasp of the definition of non-deterministic.

Same thing with quantum computers. See below.

Originally posted by: Matthias99

Another possible definition of an NP-Hard problem is one that can be solved in polynomial time non-deterministically (that is, if you know the answer in advance, you can verify its correctness in polynomial time). I believe that's what was being referred to here.

Ok, that's a term I haven't seen. But it can't be solved in polynomial time using such an algorithm, because you have a non-polynomial space to search... If you've got O(e^n) possible solutions, you can't be guaranteed to find the answer in under O(e^n) time.

You're right that it's not really correct to call a quantum computer "non-deterministic"; it is, however, exponentially parallel in the number of Q-bits available for use. This means a quantum computer containing N Q-bits can solve one of these "non-deterministic" NP-Complete problems of size N in polynomial time (in theory!)

Quantum computing can't actually reduce the time taken to solve NP-complete problems to polynomial because they'd only be polynomial up to a limit in the size of the input, the number of qubits in the computer. Remember that O(n) is the limit as n->infinity.

Perhaps I should have said the limits of algorithmic computation in our universe. My knowledge of information theory stops when astrophysics starts creeping into it.

Acutally, it's not astrophysics, it's quantum mechanics. I'm not much of an astrophysicist at all.
Astrophyisics has little relation to this phenomenon, other than the observation of black holes. It's entirely possible that black holes don't behave at all like I think they would, in which case, my (actually Penrose's) theory goes out the window.


Edit: oops, forgot to respond to definition of "non-deterministic".

 

[Matthias99]

Originally posted by: rjain

Originally posted by: Rainsford

I'm not sure I follow. As I understand it, a non-deterministic algorithm is impossible, or at least impracticle.

Non-deterministic algorithms are old hat. Late 60s or something. Any time there is a choice in your search, you randomly choose one option. If that one fails, you try the other choice.

What we're talking about here is a way of doing analysis based on non-determinism (not actually running a non-deterministic algorithm!) It's like asking "How long would it take to solve this problem if we could try every possible solution in parallel"? If the answer is "Polynomial time or less", then the problem is in NP.

Originally posted by: Matthias99

Another possible definition of an NP-Hard problem is one that can be solved in polynomial time non-deterministically (that is, if you know the answer in advance, you can verify its correctness in polynomial time). I believe that's what was being referred to here.

Ok, that's a term I haven't seen. But it can't be solved in polynomial time using such an algorithm, because you have a non-polynomial space to search... If you've got O(e^n) possible solutions, you can't be guaranteed to find the answer in under O(e^n) time.

Uh, yes. I thought we covered that above. We don't have a non-deterministic computer, but if we did, it would solve these problems in polynomial time. As you both seem to have noticed, this is not a terribly practical observation.

Quantum computing can't actually reduce the time taken to solve NP-complete problems to polynomial because they'd only be polynomial up to a limit in the size of the input, the number of qubits in the computer. Remember that O(n) is the limit as n->infinity.

It reduces the time required by a factor of (2^Q), where Q is the number of Q-bits available. Thus, it actually reduces the time required to O((2^N) / (2^Q)) = O(2^(N-Q)), where N is the size of the input and Q is the number of Q-bits. As I said:

This means a quantum computer containing N Q-bits can solve one of these "non-deterministic" NP-Complete problems of size N in polynomial time (in theory!)

The point is that the computing power of a quantum computer (in terms of Q-bits) "matches" the computing difficulty of an NP-Complete problem (in terms of input size N). The computing power of a Turing Machine-like computer (in operations) does not. I did not mean to imply that a quantum computer can solve an NP-Complete problem of any size in polynomial time. That would just be silly.

Acutally, it's not astrophysics, it's quantum mechanics. I'm not much of an astrophysicist at all.

I'm not much of a quantum mechanic.

 

[f95toli]

You can not really compare quatum computers with ordinary computers. There are only a few known algorithms that can be used with a quantum computer (the most famousbeeing Shore's algorithm for factorization, in poynomial time). To say that quantum computers "only" run a lot of calculations in parallel is a slightly missleading simplification.
We still do not know if quantum computers will be usefull for anything besides code breaking and database searches, those are the only known applications so far (it might be possible to "map" other problems to one of the known algorithms, but as far as I know no one has figured out a simple way to do this yet).

 

[tinyabs]

Originally posted by: f95toli
You can not really compare quatum computers with ordinary computers. There are only a few known algorithms that can be used with a quantum computer (the most famousbeeing Shore's algorithm for factorization, in poynomial time). To say that quantum computers "only" run a lot of calculations in parallel is a slightly missleading simplification.
We still do not know if quantum computers will be usefull for anything besides code breaking and database searches, those are the only known applications so far (it might be possible to "map" other problems to one of the known algorithms, but as far as I know no one has figured out a simple way to do this yet).

How is quantum computer different from normal computer? The talk about Q-bits, is it a tristate or multistate bit?

 

[f95toli]

I don't think it is really meaningfull to compare qubits with ordinary bits at all.
There are books that on quantum computing that deal with qubits using a "computer science"-approoach, and you can uderstand a lot about how for example the different gates (for example CNOTs) work by using theories from reversible computing (and that is also the "language" used to describe the algorithms). However, this will still only give you part of the picture since you need to understand quite a lot about quantum mechanics in order to actually understand and design new algorithms.

The Oxford centre for quantum computing has a few good tutorials on quantum computing that are quite good, www.qubit.org