Skip to main content
MathOverflow

Return to Answer

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 3

The question has basically been answered via the comments but it may help to summarize the conclusion. If you insist that the input be unclocked NP machines then nothing useful can possibly be computed from the input, as explained in the answer to this related MO question by Joel David Hamkinsthis related MO question by Joel David Hamkins. But this kind of uncomputability result is, I would argue, completely uninteresting and irrelevant to your intended question, because it has absolutely nothing at all to do with P or NP. It just amounts to the fact that arbitrary Turing machines are intractable objects. On the other hand, if the input is a clocked NP machine, then Cook's reduction shows how to construct a P machine that solves your problem (assuming P = NP). This is really what we care about in practice. If I have a problem that I know is in NP, then I want a mechanical way of producing a polytime algorithm for it (assuming P = NP). It's really irrelevant that there are all kinds of other, bizarre NP machines that accept the same language, and that it's an uncomputable task to sift through them.

The question has basically been answered via the comments but it may help to summarize the conclusion. If you insist that the input be unclocked NP machines then nothing useful can possibly be computed from the input, as explained in the answer to this related MO question by Joel David Hamkins. But this kind of uncomputability result is, I would argue, completely uninteresting and irrelevant to your intended question, because it has absolutely nothing at all to do with P or NP. It just amounts to the fact that arbitrary Turing machines are intractable objects. On the other hand, if the input is a clocked NP machine, then Cook's reduction shows how to construct a P machine that solves your problem (assuming P = NP). This is really what we care about in practice. If I have a problem that I know is in NP, then I want a mechanical way of producing a polytime algorithm for it (assuming P = NP). It's really irrelevant that there are all kinds of other, bizarre NP machines that accept the same language, and that it's an uncomputable task to sift through them.

The question has basically been answered via the comments but it may help to summarize the conclusion. If you insist that the input be unclocked NP machines then nothing useful can possibly be computed from the input, as explained in the answer to this related MO question by Joel David Hamkins. But this kind of uncomputability result is, I would argue, completely uninteresting and irrelevant to your intended question, because it has absolutely nothing at all to do with P or NP. It just amounts to the fact that arbitrary Turing machines are intractable objects. On the other hand, if the input is a clocked NP machine, then Cook's reduction shows how to construct a P machine that solves your problem (assuming P = NP). This is really what we care about in practice. If I have a problem that I know is in NP, then I want a mechanical way of producing a polytime algorithm for it (assuming P = NP). It's really irrelevant that there are all kinds of other, bizarre NP machines that accept the same language, and that it's an uncomputable task to sift through them.

Source Link
Timothy Chow
Timothy Chow
  • 82.6k
  • 26
  • 363
  • 587

The question has basically been answered via the comments but it may help to summarize the conclusion. If you insist that the input be unclocked NP machines then nothing useful can possibly be computed from the input, as explained in the answer to this related MO question by Joel David Hamkins. But this kind of uncomputability result is, I would argue, completely uninteresting and irrelevant to your intended question, because it has absolutely nothing at all to do with P or NP. It just amounts to the fact that arbitrary Turing machines are intractable objects. On the other hand, if the input is a clocked NP machine, then Cook's reduction shows how to construct a P machine that solves your problem (assuming P = NP). This is really what we care about in practice. If I have a problem that I know is in NP, then I want a mechanical way of producing a polytime algorithm for it (assuming P = NP). It's really irrelevant that there are all kinds of other, bizarre NP machines that accept the same language, and that it's an uncomputable task to sift through them.