| The Glade 4.0 https://gladerebooted.net/ |
|
| Stathole, P != NP (?!?) https://gladerebooted.net/viewtopic.php?f=2&t=3768 |
Page 1 of 1 |
| Author: | Lenas [ Mon Aug 09, 2010 12:00 pm ] |
| Post subject: | Stathole, P != NP (?!?) |
Thought Stat might enjoy this, though I'm sure we've got other math-types. Source Basically what I got out of reading, P=NP if proved true could nearly instantly solve all kinds of problems in a variety of fields. If P!=NP then we know there's not a simple solution to all of these problems in the various fields and it's going to take a lot longer to figure out. I'm probably wrong but that's the gist I got. It's only of such importance if P=NP is correct because it would advance us drastically. If proven false it'll still save a lot of really smart people time to devote to other areas. |
|
| Author: | Elmarnieh [ Mon Aug 09, 2010 12:36 pm ] |
| Post subject: | |
Yeah a coworker sent this to me this morning. I'll wait to see what peer review says of the proof. |
|
| Author: | Stathol [ Mon Aug 09, 2010 12:52 pm ] |
| Post subject: | |
I heard about this, but in all honesty, anything more than "Complexity Theory for Dummies" is well beyond my comprehension. Polynomial time (P) is fairly easy for me to comprehend, but I can't fully wrap my head around non-deterministic polynomial time (NP), because I have a hard time understanding exactly what the difference is between a non-deterministic Turing machine and a quantum computer. The difference seems to be something like the difference between non-deterministic operands vs. non-deterministic operations, but I can't quite grok it. As I understand it, one of the biggest implications of the P=NP debate is with respect to public-key cryptography. It's believed (though as far as I know, unproven) that the problem of factoring numbers belongs to the NP class. Which is to say, it is a fundamentally "difficult" problem for any deterministic computer. The lower bounds on efficiency for this type of problem are such that no computer will ever be able to solve them in a reasonable length of time if the number in question (and thus the factor space we have to search) is sufficiently large. However, verifying that a number is prime belongs to the P class of problems. Relatively speaking, we can do this very quickly. Thus, we can generate two very large prime numbers and multiply them together, and we can do this very quickly. However, someone trying to factor the resulting prime back into its two prime factors will have a very hard time of it. Public key crypto systems rely on this being true. If factorization truly does belong to NP, and if P=NP, then a sufficiently ingenuous mathematician could theoretically discover a shortcut -- a way of transforming the NP-class factorization problem into a P-class problem. This would enable us to solve factorization efficiently without the need for non-deterministic Turing machines (or even quantum computers), which would thoroughly undermine modern key distribution. Of course, public key cryptography methods weren't publicly discovered until the 1970s, so it's not as though this would send us back to the stone ages, exactly, but key distribution was becoming an intractable problem even then. Today ... it's really inconceivable due to the extent that we rely on asymmetric crypto and key exchanges being secure. Secure communications as we currently know them would come to grinding halt if someone found a way to factor numbers in polynomial time. In the mean time, Deolalikar's proof is going to be at least as controversial and difficult to substantiate as Wiles' proof of Fermat's Last Theorem. If it holds up, it's definitely one for the history books, and a lot of people are going to be letting out a big sigh of relief. On the other hand, it will mean that certain highly vexing problems are likely to remain forever beyond our reach, even if effective quantum computing becomes a reality in the near future. |
|
| Author: | Corolinth [ Mon Aug 09, 2010 1:34 pm ] |
| Post subject: | Re: |
Stathol wrote: However, someone trying to factor the resulting prime back into its two prime factors will have a very hard time of it. Are we all using the same definition of prime in regards to numbers, here?If I multiply two primes together, the result will not be prime. |
|
| Author: | Stathol [ Mon Aug 09, 2010 7:20 pm ] |
| Post subject: | |
Bleh. I meant to write "resulting number", not "resulting prime". |
|
| Page 1 of 1 | All times are UTC - 6 hours [ DST ] |
| Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |
|