3 ms·

You're really moving the goalposts here: if it's already proven that P==NP is undecidable (your supposition) then of course you couldn't prove that the algorith

by frig 17y ago

You're really moving the goalposts here: if it's already proven that P==NP is undecidable (your supposition) then of course you couldn't prove that the algorithm, say, solved arbitrary instances of SAT in time polynomial in their size; such a proof would prove P==NP => contradiction of undecidability of P==NP. I was specifically critiquing this assertion: - since it (P=?NP shown unprovable) proves that you won't ever come up with an algorithm ...which isn't exactly right (you're drawing too strong a conclusion from your supposition): in a "P==NP is undecidable" universe there's nothing (apparently) stopping there being polynomial-time algorithms for NP-complete problems, just a barrier preventing proof that a given algorithm's asymptotic performance puts it in P.

anatoly 17y ago
or - another fun possibility - you could have a provably polynomial-time algorithm that seems to solve SAT, but you can't prove or refute its correctness.
- frig 17y ago
  Actually: I think you meant what I'm saying in the earlier version of this comment. But yes: if "P==NP is undecidable" holds then for any provably-polynomial sat-"solver" the following possibilities hold: - you'd be able to find a proof it was an invalid "solver" (eg: the algorithm that assigns 'YES' to each of the N variables is provably polynomial and provably incorrect) - you wouldn't be able to find a proof it was incorrect (in a strong sense: this isn't 'because you aren't clever enough' but b/c you've stumbled upon one of the 'true' polynomial-time algorithms, ergo there can't be a valid proof it's an invalid solver) I'd guess you couldn't prove that a given polynomial-time algorithm couldn't be shown to be "provably known to be incapable of invalidation"; such a proof => doesn't exist a counterexample (in this case a SAT instance it doesn't get the right answer for), b/c such a counterexample is a refutation => proof the algorithm is correct => contradiction of "P==NP undecidable", but I won't remove the 'I'd guess' from that unless I had a better understanding of the field, as this kind of reasoning is the kind of thing where the technicalities are the important things, and I'm not up to speed on them. Thus in the "P==NP undecidable" universe if you found a creepy algorithm -- in your example provably-polynomial but not known to be correct or incorrect, but "empirically" correct over a very extended period of time -- you'd know not to waste time trying to prove it correct (b/c such a proof would be obviously impossible) but you'd see every attempt at proving it invalid also fail, like you said. Edited for clarity. Edited again for correction.
jerf 17y ago
My apologies. I misunderstood your argument. I believe that is a correct example of the "finer slicing" I was referring to.

by frig 17y ago

anatoly 17y ago

or - another fun possibility - you could have a provably polynomial-time algorithm that seems to solve SAT, but you can't prove or refute its correctness.

frig 17y ago
Actually: I think you meant what I'm saying in the earlier version of this comment. But yes: if "P==NP is undecidable" holds then for any provably-polynomial sat-"solver" the following possibilities hold: - you'd be able to find a proof it was an invalid "solver" (eg: the algorithm that assigns 'YES' to each of the N variables is provably polynomial and provably incorrect) - you wouldn't be able to find a proof it was incorrect (in a strong sense: this isn't 'because you aren't clever enough' but b/c you've stumbled upon one of the 'true' polynomial-time algorithms, ergo there can't be a valid proof it's an invalid solver) I'd guess you couldn't prove that a given polynomial-time algorithm couldn't be shown to be "provably known to be incapable of invalidation"; such a proof => doesn't exist a counterexample (in this case a SAT instance it doesn't get the right answer for), b/c such a counterexample is a refutation => proof the algorithm is correct => contradiction of "P==NP undecidable", but I won't remove the 'I'd guess' from that unless I had a better understanding of the field, as this kind of reasoning is the kind of thing where the technicalities are the important things, and I'm not up to speed on them. Thus in the "P==NP undecidable" universe if you found a creepy algorithm -- in your example provably-polynomial but not known to be correct or incorrect, but "empirically" correct over a very extended period of time -- you'd know not to waste time trying to prove it correct (b/c such a proof would be obviously impossible) but you'd see every attempt at proving it invalid also fail, like you said. Edited for clarity. Edited again for correction.

jerf 17y ago

My apologies. I misunderstood your argument. I believe that is a correct example of the "finer slicing" I was referring to.