4 ms·

Quick stats: [Equal]: 62 [Not equal]: 50 [Undecidable]: 1 [Unprovable]: 2

deleted 5y ago
[deleted]
kadoban 5y ago
Is [Unprovable] the same as [Not equal]? It seems like the only way that's possible is if P!=NP, since in the other case there's just so many proofs available (proofs be example, algos that solve any of several hundred known problems in poly time). So in a sense, any proof that there is no proof would be proof that P!=NP. Maybe I'm missing something?
- jonathanstrange 5y ago
  I think it means that neither P=NP nor P!=NP is provable.
  - kadoban 5y ago
    But is it a proof that neither is provable? Or just a statement of giving up? Assuming it's a proof, there's two cases: 1) it's really P=NP, but we can't prove it 2) it's really P!=NP, but we can't prove it If it's case 1, that's impossible. If P=NP, then there exist polytime algorithms for NP-Complete problems, and any of those algorithms are a proof that P=NP. So that's a contradiction. So the _only_ possibility given a proof that it's unprovable would be case 2, thus proving P!=NP and contradicting itself. Am I missing something? Even assuming I'm right, this isn't a proof that one of P=NP or P!=NP are provable, just that it's impossible to prove that neither can be proven.
    - lalaithion 5y ago
      Math proofs start given a set of axioms. The modern set of Axioms are ZFC. If you can find a new axiom A such that ZFC + A is a consistent system[1] and P=NP, and also find a new axiom B such that ZFC + B is a consistent system[1] and P!=NP, then logically, P?=NP cannot have a solution either way in just ZFC. [1] Assuming ZFC is itself consistent
      - kadoban 5y ago
        Are Turing machines representable in ZFC (pretty sure they are)? Seems like it'd be at least _really_ difficult to do that trick if so. That would mean that in ZFC+A there exist algorithms that can't exist in ZFC+B? Hard for me to imagine what those would even be, since they'd have to be representable in ZFC itself anyway, right, since that's all that an algorithm would be this model, a particular Turing machine?
        lalaithion 5y ago
        Yeah, there's a reason most people don't think it's independent. Still, there are a significant number of things that are independent: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent... But (I think) all of them have to do with infinity in some weird way.
- 12039192301293 5y ago
  Not sure if this applies here but generally speaking, there are things that are true but unprovable. See Gödel's Incompleteness Theorem [1]. [1] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
  - kadoban 5y ago
    Good callout, thank you. Yeah I'm aware in general that there are unprovable true things. I've somehow convinced myself that this can't be one of them, though the other thread of this I believe I'm being shown how it might be.
- throwaway81523 5y ago
  No, it's possible that there is a P-time SAT-solving algorithm A, but that it's not provable that A runs in P-time, and/or it's not provable that A actually solves SAT (even though it does). In fact there is a known and fairly simple algorithm that provably solves SAT, but its running time is unknown. It runs in P-time if and only if P=NP. It is called Levin's Universal Search and you can read about it.
ColinWright 5y ago
I'm assuming that's the stats for the "results" on the linked page. It's certainly not the stats of opinions of mathematicians in my circles.

deleted 5y ago

[deleted]

Is [Unprovable] the same as [Not equal]? It seems like the only way that's possible is if P!=NP, since in the other case there's just so many proofs available (proofs be example, algos that solve any of several hundred known problems in poly time). So in a sense, any proof that there is no proof would be proof that P!=NP. Maybe I'm missing something?

jonathanstrange 5y ago
I think it means that neither P=NP nor P!=NP is provable.
- kadoban 5y ago
  But is it a proof that neither is provable? Or just a statement of giving up? Assuming it's a proof, there's two cases: 1) it's really P=NP, but we can't prove it 2) it's really P!=NP, but we can't prove it If it's case 1, that's impossible. If P=NP, then there exist polytime algorithms for NP-Complete problems, and any of those algorithms are a proof that P=NP. So that's a contradiction. So the _only_ possibility given a proof that it's unprovable would be case 2, thus proving P!=NP and contradicting itself. Am I missing something? Even assuming I'm right, this isn't a proof that one of P=NP or P!=NP are provable, just that it's impossible to prove that neither can be proven.
  - lalaithion 5y ago
    Math proofs start given a set of axioms. The modern set of Axioms are ZFC. If you can find a new axiom A such that ZFC + A is a consistent system[1] and P=NP, and also find a new axiom B such that ZFC + B is a consistent system[1] and P!=NP, then logically, P?=NP cannot have a solution either way in just ZFC. [1] Assuming ZFC is itself consistent
    - kadoban 5y ago
      Are Turing machines representable in ZFC (pretty sure they are)? Seems like it'd be at least _really_ difficult to do that trick if so. That would mean that in ZFC+A there exist algorithms that can't exist in ZFC+B? Hard for me to imagine what those would even be, since they'd have to be representable in ZFC itself anyway, right, since that's all that an algorithm would be this model, a particular Turing machine?
      - lalaithion 5y ago
        Yeah, there's a reason most people don't think it's independent. Still, there are a significant number of things that are independent: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent... But (I think) all of them have to do with infinity in some weird way.
12039192301293 5y ago
Not sure if this applies here but generally speaking, there are things that are true but unprovable. See Gödel's Incompleteness Theorem [1]. [1] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
- kadoban 5y ago
  Good callout, thank you. Yeah I'm aware in general that there are unprovable true things. I've somehow convinced myself that this can't be one of them, though the other thread of this I believe I'm being shown how it might be.
throwaway81523 5y ago
No, it's possible that there is a P-time SAT-solving algorithm A, but that it's not provable that A runs in P-time, and/or it's not provable that A actually solves SAT (even though it does). In fact there is a known and fairly simple algorithm that provably solves SAT, but its running time is unknown. It runs in P-time if and only if P=NP. It is called Levin's Universal Search and you can read about it.

ColinWright 5y ago

I'm assuming that's the stats for the "results" on the linked page. It's certainly not the stats of opinions of mathematicians in my circles.