81–90 of 156 posts
Earlier quoted context omitted.
Here is one proof. I don't know if this can be attributed to Ramanujan. Let a, b be equal integers a = b a^2 = ab // multiply by a a^2 + a^2 - 2ab = ab + a^2 - 2ab // subtract a^2 - 2ab 2(a^2 - ab) = a^2 - ab 2 = 1 From p319, Fermat's Last Theorem by Simon Singh
division by zero ?
Earlier quoted context omitted.
To pick on a small part of your comment: Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography? It's not like a proof would suddenly make an i7 able to factor huge numbers in polynomial time. Also, while all polynomial-time algorithms are considered "tractable" in theoretical CS, that doesn't mean that they're all practical on current hardware (nor does it claim to…
Factoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time. The issue of whether it's a feasible amount of work is exactly what I was addressing.
'It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete'
So even if this showed 'P = NP-complete' it may not imply imply factorization is in P. I'm at the limits of my rusty complexity knowledge here so if any knows better please correct me.
Earlier quoted context omitted.
It's on the arXive, so you know it's legit.
Just because its on arXiv doesn't mean its legitimate. Its more likely that it is legitimate if it gets published (with a few exceptions like the Poincaré conjecture.
Guess it's time to switch my SSH key to 4096 bits ECDSA. Good bye RSA.
1. For a fixed permutation construct a Viterbi-like search on the triplet assignments - if it fails it is not satisfiable. However, if it doesn't fail right away, there is still no guarantee there is an assignment. Call this structure compact triplet (CTF) or whatever.
2. Constuct a small set of permutation (at most m) for which every clause in the original CNF failing to satisfy will mean that at least one of these permutations CTFs will fail to satisfy.
3. Efficiently? combine the structures.
I didn't really read it deeply but that from what I understood that seems to be the top level strategy. I'm not 100% certain about it.
Earlier quoted context omitted.
Factoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time. The issue of whether it's a feasible amount of work is exactly what I was addressing.
Speaking pedantically, P is in NP also. I suspect that NP is being used as shorthand for NP-complete, not just NP. As for actual deterministic factorization Wikipedia says that 'It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete' So even if this showed 'P = NP-complete' it may not imply imply factorization is in P. I'm at the limits of my rusty complexity knowledge…
Also, there are problems in NP that are neither in P, nor are they NP- or co-NP-complete.
I'm not at all an expert on this material, but some random points to get people started: 0. This guy looks orders of magnitude less looney than the usual P=NP prover. I hope someone who knows this material well steps in soon. 1. This guy has implemented his algorithm. This is a very good sign -- most garbage "algorithms" are exposed to be broken when people try to implement them. 2. Most 3SAT problems are "easy". Bei…
To pick on a small part of your comment: Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography? It's not like a proof would suddenly make an i7 able to factor huge numbers in polynomial time. Also, while all polynomial-time algorithms are considered "tractable" in theoretical CS, that doesn't mean that they're all practical on current hardware (nor does it claim to…
Earlier quoted context omitted.
Yeah, and, seriously, a Russian?! Please...
Why not a Russian? For example the Russian Mathematics Olympiad is considered harder than the International Math Olympiad by many of the top contestants. Edit: why downvoting?
Please stop, you do understand.
Earlier quoted context omitted.
Why not a Russian? For example the Russian Mathematics Olympiad is considered harder than the International Math Olympiad by many of the top contestants. Edit: why downvoting?
I interpreted dauphin's comment as sarcasm.
I'm not at all an expert on this material, but some random points to get people started: 0. This guy looks orders of magnitude less looney than the usual P=NP prover. I hope someone who knows this material well steps in soon. 1. This guy has implemented his algorithm. This is a very good sign -- most garbage "algorithms" are exposed to be broken when people try to implement them. 2. Most 3SAT problems are "easy". Bei…