3 ms·

Tangential, but for some reason P vs. NP attracts an ungodly amount of cranks, probably because as far as open problems of that importance go it's easy to under

by qsort 1y ago

Tangential, but for some reason P vs. NP attracts an ungodly amount of cranks, probably because as far as open problems of that importance go it's easy to understand the question.

CJefferson 1y ago
I agree, but think it's worse. It's easy to get a superficial understanding of the problem, and then very easy to subtly mis-understand it. I've reviewed published papers by respectable people where they've made one of several easy mistakes: * Be careful about how you encode your problem, it's easy to make it "too large", at which point your problem can be solved in P in the input size. For example, don't represent a sudoku as triples "x-pos,y-pos,value", where those 3 numbers are encoded in binary, because now if I give you a problem with only 2 filled in values, you can't take the solution as your 'certificate', as your input is about size 6 * log(n), but the solution will be n * n * log(n). * It's also easy if you write your problem as a little language to accidentally make it impossible to check in P time. * When proving a reduction (say turning SAT into a Sudoku, to prove Sudoku is NP-complete), it's (usually) easy to show how solutions map to solutions (so you show how the SAT instance's solution turns into a particular solution to the Sudoku). It's usually much harder, and easy to make mistakes, showing the Sudoku can't possible have any other solutions.
- eru 1y ago
  I've also seen people make the wrong direction of reduction. Basically, they show that you can use SAT to solve Sudoku, and then claim that this makes Sudoku NP-complete. (All it shows is that Sudoku is in NP.) People make similar mistakes often when they want to show that a certain problem isn't solvable in linear time, and they try to show that sorting can solve your problem. But it's the wrong direction.
  - dataflow 1y ago
    > Basically, they show that you can use SAT to solve Sudoku, and then claim that this makes Sudoku NP-complete. (All it shows is that Sudoku is in NP.) Wait, did you mess up the direction here too, or am I confused? If you reduce problem A to B, then it means B is at least as hard as A, because solving it would solve A. Which certainly means in this case that Sudoku is NP-hard. And it doesn't (without introducing additional facts) imply Sudoku is in NP either. I don't see anything wrong here, do you?
    - andrewla 1y ago
      No, the GP is correct. If you use SAT to solve Sudoku, you have reduced Sudoku to SAT, not the other way around. That is, you've shown that an oracle that solves any SAT problem in constant time can solve any Sudoku in polynomial time. The more difficult side is to show that for any SAT instance, you can reduce it to a Sudoku. Really proving that you can use SAT to solve Sudoku is not a great or interesting result; since Sudoku is a decision problem it is very clear that it is in NP. Or see that verifying that a Sudoku solution is correct is achievable in polynomial time.
    - mzl 1y ago
      > > they show that you can use SAT to solve Sudoku > Wait, did you mess up the direction here too, or am I confused? If you reduce problem A to B, then it means B is at least as hard as A, because solving it would solve A. Using SAT to solve Sudoku is a reduction of Sudoku to SAT. The order of the problems names switches depending on how you write it.
      - dataflow 1y ago
        Thanks, yeah, that's what I messed up. I was so focused on the reduction direction that I misparsed the statement.
    - jcranmer 1y ago
      You've messed up the direction here. Reducing unknown-complexity to NP-complete means you can bound the complexity by above, but not by below. I can reduce binary integer addition to SAT, which means that binary integer addition is no harder than SAT... but we also know by other algorithms that it is in fact easier than SAT. To bound by below, you have to reduce NP-complete (or NP-hard suffices) to unknown-complexity.
      - dataflow 1y ago
        Oh gosh. I think I was so focused on the reduction direction that I think I misread the premise of the comment -- it seems somehow my brain parsed "use SAT to solve Sudoku" as "solve SAT using Sudoku". That's why I was saying that reducing SAT to Sudoku would imply Sudoku is at least as hard as SAT. It indeed would if they had actually done that, but they did the opposite. Not sure how my wires got crossed when reading, but thanks!
- hejsansvejsan 1y ago
  There's nothing subtle about the mistake in the paper at hand. The reason everybody expects proving P != NP to be difficult is that it's very hard to say anything at all about arbitrary programs. The authors just assume without justification that any program that solves SAT must operate in a certain recursive way -- obvious rubbish. It's hard to overstate how embarrassing this is for the Springer journal where this nonsense is published.
  - Joel_Mckay 1y ago
    "Gödel's Incompleteness Theorem" https://www.youtube.com/watch?v=IuX8QMgy4qE https://www.youtube.com/watch?v=IuX8QMgy4qE Algorithmic isomorphism practically ensures most CS approaches will fail to formally model the problem clearly. To be blunt, that million dollar prize will be waiting around a long time. An infinite amount of Papers do not necessarily have to converge on a correct solution. =3
    - jojomodding 1y ago
      Gödel's Incompleteness Theorem has little to do with complexity theory. Complexity theorists routinely find out if two complexity classes are included in each other or not. Why would Gödel's Incompleteness Theorem stop them for P=NP in particular? Why is the current definition of P or NP insufficiently formal or clear? PS: Citing YouTube Videos in mathematical discussions is a big red flag indicating you have not really understood things.
      - Joel_Mckay 1y ago
        I would advise listening to Professor Thorsten Altenkirch brief introduction about the subject, and consider delaying argumentum ad hominem opinions a few minutes. > "not really understood things" Something currently impossible to prove is by definition confusing. lol =3 https://www.youtube.com/watch?v=aNSHZG9blQQ https://www.youtube.com/watch?v=aNSHZG9blQQ
        jojomodding 1y ago
andrewla 1y ago
I think both easy to understand, and also it seems very obvious that non-deterministic Turing machines are more powerful than deterministic ones. It feels almost like a non-deterministic Turing machine is more powerful almost in the sense that a halting oracle is more powerful. The insane thing is that non-deterministic Turing machines are computable at all! It really feels like they belong to a different class of "magical" computers, or an axiom-of-choice / Banach-Tarski naval-gazing infeasible trick. You mean, you just "guess" the answers and your program will get the right answer? But they are computable; the Church-Turing model of computation is fantastically powerful. Now the problem is just "feasibility" and "complexity". It seems to the initiate that there must be an answer hiding just around the next corner because it's SO OBVIOUS but in the end if you give someone n^100 time they can solve any problem that you care to pose but that still counts as P, so you're not going to stumble upon some grand insight.

by qsort 1y ago

Tangential, but for some reason P vs. NP attracts an ungodly amount of cranks, probably because as far as open problems of that importance go it's easy to understand the question.

CJefferson 1y ago

I agree, but think it's worse. It's easy to get a superficial understanding of the problem, and then very easy to subtly mis-understand it. I've reviewed published papers by respectable people where they've made one of several easy mistakes: * Be careful about how you encode your problem, it's easy to make it "too large", at which point your problem can be solved in P in the input size. For example, don't represent a sudoku as triples "x-pos,y-pos,value", where those 3 numbers are encoded in binary, because now if I give you a problem with only 2 filled in values, you can't take the solution as your 'certificate', as your input is about size 6 * log(n), but the solution will be n * n * log(n). * It's also easy if you write your problem as a little language to accidentally make it impossible to check in P time. * When proving a reduction (say turning SAT into a Sudoku, to prove Sudoku is NP-complete), it's (usually) easy to show how solutions map to solutions (so you show how the SAT instance's solution turns into a particular solution to the Sudoku). It's usually much harder, and easy to make mistakes, showing the Sudoku can't possible have any other solutions.

eru 1y ago
I've also seen people make the wrong direction of reduction. Basically, they show that you can use SAT to solve Sudoku, and then claim that this makes Sudoku NP-complete. (All it shows is that Sudoku is in NP.) People make similar mistakes often when they want to show that a certain problem isn't solvable in linear time, and they try to show that sorting can solve your problem. But it's the wrong direction.
- dataflow 1y ago
  > Basically, they show that you can use SAT to solve Sudoku, and then claim that this makes Sudoku NP-complete. (All it shows is that Sudoku is in NP.) Wait, did you mess up the direction here too, or am I confused? If you reduce problem A to B, then it means B is at least as hard as A, because solving it would solve A. Which certainly means in this case that Sudoku is NP-hard. And it doesn't (without introducing additional facts) imply Sudoku is in NP either. I don't see anything wrong here, do you?
  - andrewla 1y ago
    No, the GP is correct. If you use SAT to solve Sudoku, you have reduced Sudoku to SAT, not the other way around. That is, you've shown that an oracle that solves any SAT problem in constant time can solve any Sudoku in polynomial time. The more difficult side is to show that for any SAT instance, you can reduce it to a Sudoku. Really proving that you can use SAT to solve Sudoku is not a great or interesting result; since Sudoku is a decision problem it is very clear that it is in NP. Or see that verifying that a Sudoku solution is correct is achievable in polynomial time.
  - mzl 1y ago
    > > they show that you can use SAT to solve Sudoku > Wait, did you mess up the direction here too, or am I confused? If you reduce problem A to B, then it means B is at least as hard as A, because solving it would solve A. Using SAT to solve Sudoku is a reduction of Sudoku to SAT. The order of the problems names switches depending on how you write it.
    - dataflow 1y ago
      Thanks, yeah, that's what I messed up. I was so focused on the reduction direction that I misparsed the statement.
  - jcranmer 1y ago
    You've messed up the direction here. Reducing unknown-complexity to NP-complete means you can bound the complexity by above, but not by below. I can reduce binary integer addition to SAT, which means that binary integer addition is no harder than SAT... but we also know by other algorithms that it is in fact easier than SAT. To bound by below, you have to reduce NP-complete (or NP-hard suffices) to unknown-complexity.
    - dataflow 1y ago
      Oh gosh. I think I was so focused on the reduction direction that I think I misread the premise of the comment -- it seems somehow my brain parsed "use SAT to solve Sudoku" as "solve SAT using Sudoku". That's why I was saying that reducing SAT to Sudoku would imply Sudoku is at least as hard as SAT. It indeed would if they had actually done that, but they did the opposite. Not sure how my wires got crossed when reading, but thanks!
hejsansvejsan 1y ago
There's nothing subtle about the mistake in the paper at hand. The reason everybody expects proving P != NP to be difficult is that it's very hard to say anything at all about arbitrary programs. The authors just assume without justification that any program that solves SAT must operate in a certain recursive way -- obvious rubbish. It's hard to overstate how embarrassing this is for the Springer journal where this nonsense is published.
- Joel_Mckay 1y ago
  "Gödel's Incompleteness Theorem" https://www.youtube.com/watch?v=IuX8QMgy4qE https://www.youtube.com/watch?v=IuX8QMgy4qE Algorithmic isomorphism practically ensures most CS approaches will fail to formally model the problem clearly. To be blunt, that million dollar prize will be waiting around a long time. An infinite amount of Papers do not necessarily have to converge on a correct solution. =3
  - jojomodding 1y ago
    Gödel's Incompleteness Theorem has little to do with complexity theory. Complexity theorists routinely find out if two complexity classes are included in each other or not. Why would Gödel's Incompleteness Theorem stop them for P=NP in particular? Why is the current definition of P or NP insufficiently formal or clear? PS: Citing YouTube Videos in mathematical discussions is a big red flag indicating you have not really understood things.
    - Joel_Mckay 1y ago
      I would advise listening to Professor Thorsten Altenkirch brief introduction about the subject, and consider delaying argumentum ad hominem opinions a few minutes. > "not really understood things" Something currently impossible to prove is by definition confusing. lol =3 https://www.youtube.com/watch?v=aNSHZG9blQQ https://www.youtube.com/watch?v=aNSHZG9blQQ
      - jojomodding 1y ago

andrewla 1y ago

I think both easy to understand, and also it seems very obvious that non-deterministic Turing machines are more powerful than deterministic ones. It feels almost like a non-deterministic Turing machine is more powerful almost in the sense that a halting oracle is more powerful. The insane thing is that non-deterministic Turing machines are computable at all! It really feels like they belong to a different class of "magical" computers, or an axiom-of-choice / Banach-Tarski naval-gazing infeasible trick. You mean, you just "guess" the answers and your program will get the right answer? But they are computable; the Church-Turing model of computation is fantastically powerful. Now the problem is just "feasibility" and "complexity". It seems to the initiate that there must be an answer hiding just around the next corner because it's SO OBVIOUS but in the end if you give someone n^100 time they can solve any problem that you care to pose but that still counts as P, so you're not going to stumble upon some grand insight.