Hacker News

points by novaRom 3 days ago | 0 comments

For me, this result is significant. It basically adds much more hope P is equal NP (that majority seems being against). I believe one day AI will explain a major flaw in modern mathematics, so a kind of correction in axioms will be suggested to prove Rieman's hypothesis (or a completely new apparatus)

[–] rcpt 3 days ago

I don't know if that's a "flaw". It's what Godel Incompleteness guarantees.

Would be funny if the most famous problem turns out be an example though

[–] skew-aberration 3 days ago

That's not that how that works btw. The incompleteness is a property of the algorithm which does the proofs, not the theorems. If a theorem is true it has a proof and a program which proves it (printf("the proof verbatim")). But no computer program can successfully prove all theorems. The space of potential proofs is too big to search systematically, but you can still get lucky.

[–] noslenwerdna 3 days ago

That is also not how it works. The theorem says that there exist some true statements for which there is no proof. This is assuming the axioms are consistent.

[–] skew-aberration 3 days ago

I think you're right, I'm conflating two separate things.

EDIT: I am wrong (it's been a while) but there is nuance.

I said any computer program fails to prove some true statements. In fact, some 'true' statements cannot be proven by any program, as others have said.

But for those statements G, you can prove 'G is true if our system is consistent', just not 'G is true'.

So when we say G is 'true', we are really just asserting the consistency axiom that our computer program is denied.

[–] rcpt 3 days ago

Godel says that there are statements that are true but have no proof within that system. It's not about algorithms.

I'm saying it'd be funny if Riemann were true but not proveable.

Though I guess it's actually funnier. If Riemann were false then there would be a counterexample, so it's clearly within existing axioms.

So if one can prove that Riemann isn't proveable in our current axioms then it has to be true.

[–] plagiarist 3 days ago

Can something be both true and unprovable without being a self-referential Godel sentence? I assume most statements that aren't self-referential are independent, like the continuum hypothesis with ZFC.

[–] skew-aberration 3 days ago

Godel sentences are only true if you assume consistency. And once you add that axiom, the computer can prove them too.

G is independent of your original system T (cannot be proven true or false).

If you create T+ with added consistency axiom, then G is true and provable.

But G is never true and unprovable in the same system.

It's a lot like is/ought or theology.

[–] _dain_ 3 days ago

Why do you "hope" P=NP? It would be a catastrophe

[–] jibalt 3 days ago

Either P=NP or not. Hoping one way or the other changes nothing. Nor does it change how efficient computing is, nor does it have any effect on cryptography. Discovering a vastly more efficient means of factoring primes--perhaps via quantum computing--would do that. But just learning that P=NP does nothing to further such a discovery. Almost certainly, if P=NP, the exponents and/or constants in a polynomial factoring algorithm would be galactic. (FWIW, Knuth believes that P=NP and that it has no practical consequences.)

[–] coliveira 3 days ago

Why? Nature doesn't care if people are making financial transactions based on flawed cryptography.

[–] 80fj0348i 3 days ago

Have you been in nature? It's cold and full of bugs and disease.

[–] rcpt 3 days ago

Not really. P=NP but the degree of the polynomial is Grahams number doesn't let people into your bank account

[–] andriy_koval 3 days ago

it could make lots of compute way more efficient, not sure why it is catastrophe..