4 ms·

Sorry if this is obvious, but why does the pseudocode above actually run in nondeterministic polynomial time? What exactly is this "guess" function (is it just

Sorry if this is obvious, but why does the pseudocode above actually run in nondeterministic polynomial time? What exactly is this "guess" function (is it just a random number, or do we not know what it is?) ? Is that a guessing black box reusable for all problems? As a side question (sorry probably newbie question), why can't we just use nondeterministic turing machines to achieve what we want? (i.e. introduce optional randomness at the circuit level)

mikeash 11y ago
A nondeterministic Turing machine can be thought of as a machine that can try all possibilities at once. In this conception, it's the ultimate parallel computer. In this conception, the guess function is actually trying all possibilities for the number d, and if any of those possibilities is a match, it says so. Another way of thinking about it is as pure magic. If there is a number that's a match, then that number comes out of the "guess" function somehow. As for why we can't use a nondeterministic Turing machine to achieve what we want, it's because nobody knows how to build one. They're the computing equivalent of a frictionless pulley or a mathematical point: a useful abstraction, but not something you can actually construct. If anyone ever figures out how to send information back in time then it may be possible, but absent that we're stuck with the regular kind of Turing machine.
teraflop 11y ago
It's only obvious if you're familiar with what exactly a "nondeterministic" machine actually is. It doesn't mean random! Given a deterministic machine (let's say a Turing machine, but the same concept can be applied to more restrictive settings like FSMs or pushdown automata) there's an often-unstated assumption on how we use the machine to solve a problem. We let the machine run until it halts, and then we look at the final state. For decision problems, we usually define a special "accepting" state and say the answer is YES iff the machine halts in that state. For non-deterministic machines, we allow multiple possible transitions from any given state. So "look at the final state" is no longer meaningful, because now there are many possible sequences of states the machine could follow. Instead, we say that the machine returns an answer of YES iff there is some allowed sequence of transitions that ends in the accepting state. This is an entirely theoretical concept; the answer to "why don't we just solve problems using nondeterministic TMs?" is "because we have no reason to think it's physically possible for them to exist." (You can simulate them -- just keep track of all of the possible execution paths and check them one-by-one. But then any notion of efficiency goes out the window, because the number of paths grows exponentially, causing the amount of work required to simulate a single timestep to grow without bound.) If you think about it the right way, this formal definition captures what it means to say that the power of a nondeterministic machine is the ability to "guess correctly". In the algorithm described above, if there exists some d that divides n, then d is composite. We don't know what the value of d is, but if we had a nondeterministic machine, we could just explore all possible choices. If one of them turns out to work, then that path ends in an accepting state, so the machine returns YES. Maybe the "guess magically" function is implemented as: value = 0 while (value < n) { nondeterministically { return value } or { value++ } } Hopefully this conveys a sense of why P==NP is considered so unlikely. It would amount to a magic wand that we could wave over any of a very large class of "brute-force"-looking problems, allowing us to answer a question about exponentially many execution paths in sub-exponential time.
- darkmighty 11y ago
  Oh thank you very much, this changed my understanding of NP and what the fuss is all about (I was thinking more of a TM which has access to randomness, as the name suggests for me). I think need to read more about precisely what "multiple possible transitions from any given state" allows. Btw, is there a class that is actually "Turing machines with randomness in polynomial time" and is it more powerful than "Turing machines in polynomial time"?
  - teraflop 11y ago
    Excellent question! We call those "probabilistic Turing machines", and the most interesting complexity classes associated with them are ZPP and BPP. ZPP contains problems for which the answer is guaranteed to be correct, and the machine halts in expected polynomial time -- the so-called "Las Vegas" algorithms. And then there's BPP, containing algorithms which always run in polynomial time but whose outputs have a constant, bounded probability of being wrong -- the "Monte Carlo" algorithms. Currently, we know that P ⊆ ZPP ⊆ BPP, but we haven't yet proved whether or not any of those classes are equal to each other. However, there's apparently mounting evidence -- most of which goes over my head -- that in fact P=BPP; in other words, any randomized algorithm can be "derandomized" with the use of a sufficiently strong pseudorandom number generator.
    - darkmighty 11y ago
      Ah that's interesting, ill read more on those. But did we just come back full circle and the existence of strong pseudorandom generators depends on P!=NP? :P ( P!=NP => BPP=P => P=BPP!=NP ?)

mikeash 11y ago

A nondeterministic Turing machine can be thought of as a machine that can try all possibilities at once. In this conception, it's the ultimate parallel computer. In this conception, the guess function is actually trying all possibilities for the number d, and if any of those possibilities is a match, it says so. Another way of thinking about it is as pure magic. If there is a number that's a match, then that number comes out of the "guess" function somehow. As for why we can't use a nondeterministic Turing machine to achieve what we want, it's because nobody knows how to build one. They're the computing equivalent of a frictionless pulley or a mathematical point: a useful abstraction, but not something you can actually construct. If anyone ever figures out how to send information back in time then it may be possible, but absent that we're stuck with the regular kind of Turing machine.

teraflop 11y ago

It's only obvious if you're familiar with what exactly a "nondeterministic" machine actually is. It doesn't mean random! Given a deterministic machine (let's say a Turing machine, but the same concept can be applied to more restrictive settings like FSMs or pushdown automata) there's an often-unstated assumption on how we use the machine to solve a problem. We let the machine run until it halts, and then we look at the final state. For decision problems, we usually define a special "accepting" state and say the answer is YES iff the machine halts in that state. For non-deterministic machines, we allow multiple possible transitions from any given state. So "look at the final state" is no longer meaningful, because now there are many possible sequences of states the machine could follow. Instead, we say that the machine returns an answer of YES iff there is some allowed sequence of transitions that ends in the accepting state. This is an entirely theoretical concept; the answer to "why don't we just solve problems using nondeterministic TMs?" is "because we have no reason to think it's physically possible for them to exist." (You can simulate them -- just keep track of all of the possible execution paths and check them one-by-one. But then any notion of efficiency goes out the window, because the number of paths grows exponentially, causing the amount of work required to simulate a single timestep to grow without bound.) If you think about it the right way, this formal definition captures what it means to say that the power of a nondeterministic machine is the ability to "guess correctly". In the algorithm described above, if there exists some d that divides n, then d is composite. We don't know what the value of d is, but if we had a nondeterministic machine, we could just explore all possible choices. If one of them turns out to work, then that path ends in an accepting state, so the machine returns YES. Maybe the "guess magically" function is implemented as: value = 0 while (value < n) { nondeterministically { return value } or { value++ } } Hopefully this conveys a sense of why P==NP is considered so unlikely. It would amount to a magic wand that we could wave over any of a very large class of "brute-force"-looking problems, allowing us to answer a question about exponentially many execution paths in sub-exponential time.

darkmighty 11y ago
Oh thank you very much, this changed my understanding of NP and what the fuss is all about (I was thinking more of a TM which has access to randomness, as the name suggests for me). I think need to read more about precisely what "multiple possible transitions from any given state" allows. Btw, is there a class that is actually "Turing machines with randomness in polynomial time" and is it more powerful than "Turing machines in polynomial time"?
- teraflop 11y ago
  Excellent question! We call those "probabilistic Turing machines", and the most interesting complexity classes associated with them are ZPP and BPP. ZPP contains problems for which the answer is guaranteed to be correct, and the machine halts in expected polynomial time -- the so-called "Las Vegas" algorithms. And then there's BPP, containing algorithms which always run in polynomial time but whose outputs have a constant, bounded probability of being wrong -- the "Monte Carlo" algorithms. Currently, we know that P ⊆ ZPP ⊆ BPP, but we haven't yet proved whether or not any of those classes are equal to each other. However, there's apparently mounting evidence -- most of which goes over my head -- that in fact P=BPP; in other words, any randomized algorithm can be "derandomized" with the use of a sufficiently strong pseudorandom number generator.
  - darkmighty 11y ago
    Ah that's interesting, ill read more on those. But did we just come back full circle and the existence of strong pseudorandom generators depends on P!=NP? :P ( P!=NP => BPP=P => P=BPP!=NP ?)