4 ms·

I think you picked a bad example, because the "computation" in NP is not really a computation to most of us. Most programmers think that computation means "som

by btilly 3y ago

I think you picked a bad example, because the "computation" in NP is not really a computation to most of us. Most programmers think that computation means "something that can be done on a Turing machine or equivalent". It isn't hard to extend this idea to things like a true random number generator, or a quantum computer. This shows your basic point that computation need not be deterministic. But the "nondeterministic" in NP doesn't speak to an actual computation that programmers think can be done. It speaks to a computation that we'd like to be able to do, but most of us think can't be done. (There is a prize for proving that impossibility.) And while there might be models of computation where said computation can be done, few programmers would think of them as modeling an actual computation. Here alert readers might jump up and say, "Quantum computers might be able to solve NP complete problems!" True, we don't have a proof that it is impossible. But at the present time, there is no reason to believe that it is possible either. See, for instance, https://www.scottaaronson.com/papers/npcomplete.pdf https://www.scottaaronson.com/papers/npcomplete.pdf. And so it appears that for actual computers that can be built, there is no computation matching how we'd like to solve NP complete problems.

tsimionescu 3y ago
I was mainly trying to point out that the mathematical term "computation" is not limited to deterministic computers. Since the GP was mentioning computable functions as something requiring determinism, I believe they were also talking more about the mathematical notion of computation rather than physical computers. I should also note that our computers can very much solve NP-complete problems. They can't implement NP-complete algorithms to solve them, but all NP problems can be solved by a deterministic computer or a quantum computer - it just takes [much] more compute time (assuming P != NP, otherwise it may even take the same time). This is very relevant to this discussion, because in fact it is well known and proven that the non-determinism in the NP model does not give any amount of extra computational power beyond a Turing machine. That is, a non-determinstic Turing machine can solve exactly the same set of problems as a deterministic Turing machine (but, as far as it is known today, faster). The same is true of Quantum computers. Hyper-computation refers to even more fanciful mathematical models which are actually able to solve problems that a Turing machine can't solve, even with infinite time. They involve things like performing an infinite amount of Turing machine steps in one Hyper-Turing machine step, or having access to an oracle which tells you if a computation halts etc.
- btilly 3y ago
  Yes, you can have fanciful "models of computation" with oracles of various kinds. Few people really think of that as computation. But I agree that there are real examples of physically possible computation which are not deterministic. The most widely used being true random number generators. And so theoretical computability is not necessarily the right model for the real world.
  - tsimionescu 3y ago
    Note that analyzing the complexity of problems in relation to various oracles is probably half of computer science. Algorithms like those in NP are not exotic concepts, they are the bread and butter of many computer science courses and careers. Hyper-computation is much more exotic, though, I'll give you that.
  - mjburgess 3y ago
    Random number generation, if physically non-deterministic, isnt computation. https://en.wikipedia.org/wiki/Computable_function https://en.wikipedia.org/wiki/Computable_function
readams 3y ago
The "nondeterministic" in NP ("Nondeterministic polynomial") means that problems in NP can be solved in polynomial time by a nondeterministic Turing machine. Such a machine would be like what people incorrectly think quantum computers would be, in the sense that it would explore all the possible paths at once. It's the same meaning as in a nondeterministic finite automaton (NFA) vs a deterministic finite automaton (DFA). The question of P vs NP is not whether we haven't determined if we can do a particular computation (either at all or in polynomial time). It's whether a deterministic Turing machine could solve in polynomial time the same class of problems that we _know_ a nondeterministic Turing machine could solve in polynomial time. Of course, the nondeterministic Turing machine is not a physically realistic model of computation.
- btilly 3y ago
  I'm trying to figure out whether you're just trying to echo what I said in different words, or whether you thought that you were correcting what I said. If the latter, please be specific about what misunderstanding you think I might have.

by btilly 3y ago

tsimionescu 3y ago

I was mainly trying to point out that the mathematical term "computation" is not limited to deterministic computers. Since the GP was mentioning computable functions as something requiring determinism, I believe they were also talking more about the mathematical notion of computation rather than physical computers. I should also note that our computers can very much solve NP-complete problems. They can't implement NP-complete algorithms to solve them, but all NP problems can be solved by a deterministic computer or a quantum computer - it just takes [much] more compute time (assuming P != NP, otherwise it may even take the same time). This is very relevant to this discussion, because in fact it is well known and proven that the non-determinism in the NP model does not give any amount of extra computational power beyond a Turing machine. That is, a non-determinstic Turing machine can solve exactly the same set of problems as a deterministic Turing machine (but, as far as it is known today, faster). The same is true of Quantum computers. Hyper-computation refers to even more fanciful mathematical models which are actually able to solve problems that a Turing machine can't solve, even with infinite time. They involve things like performing an infinite amount of Turing machine steps in one Hyper-Turing machine step, or having access to an oracle which tells you if a computation halts etc.

btilly 3y ago
Yes, you can have fanciful "models of computation" with oracles of various kinds. Few people really think of that as computation. But I agree that there are real examples of physically possible computation which are not deterministic. The most widely used being true random number generators. And so theoretical computability is not necessarily the right model for the real world.
- tsimionescu 3y ago
  Note that analyzing the complexity of problems in relation to various oracles is probably half of computer science. Algorithms like those in NP are not exotic concepts, they are the bread and butter of many computer science courses and careers. Hyper-computation is much more exotic, though, I'll give you that.
- mjburgess 3y ago
  Random number generation, if physically non-deterministic, isnt computation. https://en.wikipedia.org/wiki/Computable_function https://en.wikipedia.org/wiki/Computable_function

readams 3y ago

The "nondeterministic" in NP ("Nondeterministic polynomial") means that problems in NP can be solved in polynomial time by a nondeterministic Turing machine. Such a machine would be like what people incorrectly think quantum computers would be, in the sense that it would explore all the possible paths at once. It's the same meaning as in a nondeterministic finite automaton (NFA) vs a deterministic finite automaton (DFA). The question of P vs NP is not whether we haven't determined if we can do a particular computation (either at all or in polynomial time). It's whether a deterministic Turing machine could solve in polynomial time the same class of problems that we _know_ a nondeterministic Turing machine could solve in polynomial time. Of course, the nondeterministic Turing machine is not a physically realistic model of computation.

btilly 3y ago
I'm trying to figure out whether you're just trying to echo what I said in different words, or whether you thought that you were correcting what I said. If the latter, please be specific about what misunderstanding you think I might have.