6 ms·

Well, it would also be very strange if P=NP because you could use algorithms like this in polynomial time: bool isComposite(n) { guess a number d magical

Well, it would also be very strange if P=NP because you could use algorithms like this in polynomial time: bool isComposite(n) { guess a number d magically if (n % d == 0) { return true; } else { fail; } }

mikeash 11y ago
P = NP just means that there exist some polynomial-time algorithm that's able to solve that problem. It doesn't mean that you can take that pseudocode and run it directly in polynomial time.
- teraflop 11y ago
  Actually, it kind of does. If P==NP, then any problem in NP is solvable in polynomial time -- including efficient simulation of a non-deterministic Turing machine that supports "guessing correctly" as a primitive operation. That's why the P=?NP problem has such far-reaching implications, and one reason why P==NP is generally believed to be false.
  - 1arity 11y ago
    What's the reduction from 3-SAT to "guessing correctly"?
    - teraflop 11y ago
      The original reduction was given by the well-known Cook-Levin theorem. It's really the existence of this theorem that motivated the entire study of NP-complete problems in the first place. Basically, you can unroll the execution of a non-deterministic Turing machine along the time axis, using separate variables to represent the state of the machine at each time step. All of the rules that govern the Turing machine's execution can be encoded as Boolean formulas, resulting in one giant formula such that the formula is satisfiable iff there is an assignment of variables corresponding to a valid execution. Adding non-determinism (the "guessing") is easy; you just leave particular variables unconstrained. If the original machine runs in polynomial time, then the number of variables and clauses is also polynomial. And of course there's a straightforward polynomial reduction from SAT to 3-SAT. No offense, but if you don't already know about this, it's kind of ironic that you're the one claiming CS researchers are "arrogant" for their beliefs about P=?NP.
  - mikeash 11y ago
    Is efficient simulation of a nondeterministic Turing machine in NP? I don't see how that could be the case. These are decision problems, where you pose a yes/no question, and you get an answer. If a decision problem is in P, then you get your yes/no answer in polynomial time when run on a normal Turing machine. If it's in NP, then you get your yes/no answer in polynomial time when run on a nondeterministic Turing machine. What would be the yes/no answer for "simulation of a non-deterministic Turing machine"? If it's just "the yes/no answer provided by whatever that Turing machine runs" then that problem is clearly not in NP, since you could easily have some code that takes more than polynomial time. Can you restrict it to "the yes/no answer provided by whatever that Turing machine runs, provided that it runs in polynomial time"?
    - teraflop 11y ago
      Well, that comes back to the definition of NP. A problem is in NP iff it is solvable by a non-deterministic Turing machine that is guaranteed to run in polynomial time. If such a machine exists, and P==NP, then the problem is also solvable by a deterministic Turing machine in polynomial time. Strictly speaking, the proof assumes a particular Turing machine. But since universal Turing machines exist, we can equivalently say: if P==NP then there exists a deterministic program that takes a description of a non-deterministic TM and an input string, such that if the non-deterministic TM halts in polynomial time, so does the deterministic algorithm (with the same answer). (The standard proof of the Cook-Levin theorem assumes that you actually have a polynomial bound on the number of time steps, rather than simply being assured that one exists. This is a technical detail that can be worked around by e.g. doubling the number of steps exponentially until you detect termination.)
      - mikeash 11y ago
        Thanks for this, and especially your other comment where you sketched the reduction. I don't entirely see how it falls out of the definition of NP like you say, but your sketch makes a lot of sense for how to make it happen. Just to make sure I got this right, the basic idea is: simulate the non-deterministic Turing machine using boolean variables, with unconstrained variables for the nondeterministic part. Sort of a symbolic execution on a Turing machine. Convert the simulation to a boolean expression. Convert the boolean expression to 3-SAT form. Put 3-SAT problem into your magical P==NP machine and get an answer out. You've now found the answer given by the nondeterministic Turing machine in polynomial time, if the original would indeed run in polynomial time.
  - VLM 11y ago
    A non-constructive proof would be hilarious. Or something constructable that works out to big-oh N to the trillionth.
    - _asummers 11y ago
      Oddly enough, Knuth believes this to be true. http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858
  - darkmighty 11y ago
    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.
BrainInAJar 11y ago
primality testing is a poor example. PRIMES is in P. http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v...
- _asummers 11y ago
  Even factoring would be a poor example, given that it has never been shown to be NP-complete.
  - BrainInAJar 11y ago
    It would be very surprising if it were, since it's also in co-NP. The other problems in NP intersect co-NP are all in P. It's not at all unlikely, and a lot of evidence points towards, that integer factorization is in P.

mikeash 11y ago

P = NP just means that there exist some polynomial-time algorithm that's able to solve that problem. It doesn't mean that you can take that pseudocode and run it directly in polynomial time.

teraflop 11y ago
Actually, it kind of does. If P==NP, then any problem in NP is solvable in polynomial time -- including efficient simulation of a non-deterministic Turing machine that supports "guessing correctly" as a primitive operation. That's why the P=?NP problem has such far-reaching implications, and one reason why P==NP is generally believed to be false.
- 1arity 11y ago
  What's the reduction from 3-SAT to "guessing correctly"?
  - teraflop 11y ago
    The original reduction was given by the well-known Cook-Levin theorem. It's really the existence of this theorem that motivated the entire study of NP-complete problems in the first place. Basically, you can unroll the execution of a non-deterministic Turing machine along the time axis, using separate variables to represent the state of the machine at each time step. All of the rules that govern the Turing machine's execution can be encoded as Boolean formulas, resulting in one giant formula such that the formula is satisfiable iff there is an assignment of variables corresponding to a valid execution. Adding non-determinism (the "guessing") is easy; you just leave particular variables unconstrained. If the original machine runs in polynomial time, then the number of variables and clauses is also polynomial. And of course there's a straightforward polynomial reduction from SAT to 3-SAT. No offense, but if you don't already know about this, it's kind of ironic that you're the one claiming CS researchers are "arrogant" for their beliefs about P=?NP.
- mikeash 11y ago
  Is efficient simulation of a nondeterministic Turing machine in NP? I don't see how that could be the case. These are decision problems, where you pose a yes/no question, and you get an answer. If a decision problem is in P, then you get your yes/no answer in polynomial time when run on a normal Turing machine. If it's in NP, then you get your yes/no answer in polynomial time when run on a nondeterministic Turing machine. What would be the yes/no answer for "simulation of a non-deterministic Turing machine"? If it's just "the yes/no answer provided by whatever that Turing machine runs" then that problem is clearly not in NP, since you could easily have some code that takes more than polynomial time. Can you restrict it to "the yes/no answer provided by whatever that Turing machine runs, provided that it runs in polynomial time"?
  - teraflop 11y ago
    Well, that comes back to the definition of NP. A problem is in NP iff it is solvable by a non-deterministic Turing machine that is guaranteed to run in polynomial time. If such a machine exists, and P==NP, then the problem is also solvable by a deterministic Turing machine in polynomial time. Strictly speaking, the proof assumes a particular Turing machine. But since universal Turing machines exist, we can equivalently say: if P==NP then there exists a deterministic program that takes a description of a non-deterministic TM and an input string, such that if the non-deterministic TM halts in polynomial time, so does the deterministic algorithm (with the same answer). (The standard proof of the Cook-Levin theorem assumes that you actually have a polynomial bound on the number of time steps, rather than simply being assured that one exists. This is a technical detail that can be worked around by e.g. doubling the number of steps exponentially until you detect termination.)
    - mikeash 11y ago
      Thanks for this, and especially your other comment where you sketched the reduction. I don't entirely see how it falls out of the definition of NP like you say, but your sketch makes a lot of sense for how to make it happen. Just to make sure I got this right, the basic idea is: simulate the non-deterministic Turing machine using boolean variables, with unconstrained variables for the nondeterministic part. Sort of a symbolic execution on a Turing machine. Convert the simulation to a boolean expression. Convert the boolean expression to 3-SAT form. Put 3-SAT problem into your magical P==NP machine and get an answer out. You've now found the answer given by the nondeterministic Turing machine in polynomial time, if the original would indeed run in polynomial time.
- VLM 11y ago
  A non-constructive proof would be hilarious. Or something constructable that works out to big-oh N to the trillionth.
  - _asummers 11y ago
    Oddly enough, Knuth believes this to be true. http://www.informit.com/articles/article.aspx?p=2213858 http://www.informit.com/articles/article.aspx?p=2213858
- darkmighty 11y ago
  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.

BrainInAJar 11y ago

primality testing is a poor example. PRIMES is in P. http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v...

_asummers 11y ago
Even factoring would be a poor example, given that it has never been shown to be NP-complete.
- BrainInAJar 11y ago
  It would be very surprising if it were, since it's also in co-NP. The other problems in NP intersect co-NP are all in P. It's not at all unlikely, and a lot of evidence points towards, that integer factorization is in P.