SciTechDaily: The Million Dollar Problem That Could Break Cryptography
SciTechDaily: The Million Dollar Problem That Could Break Cryptography. https://scitechdaily.com/the-million-dollar-problem-that-could-break-cryptog... Usually, you can verify a solution to a problem. Whether it’s using multiplication for division or plugging the answer in for a variable, math teachers tell you to check your work using your answer in every school math class. But let’s say you can verify a solution easily, is it just as easy to solve for that solution? This is the P versus NP problem, a Millenium Prize Problem where the solver will receive a million dollars if valid proof is provided. What is P versus NP? In computer science, the efficiency of algorithms is very important. Most algorithms are believed to be “fast” if solvable in a standard called polynomial time. Polynomial time is when a problem is solvable in steps scaled by a factor of a polynomial given the complexity of input. So let’s say the complexity of input is some number n, a polynomial time algorithm will be able to solve a problem in nk steps. Essentially, P vs NP is asking the question: Are problems that can have solutions verified in polynomial time, also have their answers solved in polynomial time? NP-Completeness An Euler Diagram showing the cases for NP-Completeness for P ≠ NP and P = NP. Credit: Behnam Esfahbod, Wikimedia Commons (CC
Thanks Gym!
------- Original Message -------
On Thursday, August 4th, 2022 at 12:41 AM, jim bell
SciTechDaily: The Million Dollar Problem That Could Break Cryptography. https://scitechdaily.com/the-million-dollar-problem-that-could-break-cryptog...
Usually, you can verify a solution to a problem. Whether it’s using multiplication for division or plugging the answer in for a variable, math teachers tell you to check your work using your answer in every school math class.
But let’s say you can verify a solution easily, is it just as easy to solve for that solution?
This is the P versus NP problem, a Millenium Prize Problem where the solver will receive a million dollars if valid proof is provided.
What is P versus NP?
In computer science, the efficiency of algorithms is very important. Most algorithms are believed to be “fast” if solvable in a standard called polynomial time. Polynomial time is when a problem is solvable in steps scaled by a factor of a polynomial given the complexity of input. So let’s say the complexity of input is some number n, a polynomial time algorithm will be able to solve a problem in nk steps.
Essentially, P vs NP is asking the question: Are problems that can have solutions verified in polynomial time, also have their answers solved in polynomial time?
NP-Completeness
[P versus NP](https://scitechdaily.com/images/P-versus-NP.jpg)
An Euler Diagram showing the cases for NP-Completeness for P ≠ NP and P = NP. Credit: Behnam Esfahbod, Wikimedia Commons [(CC](https://creativecommons.org/licenses/by-sa/3.0/)
participants (2)
-
Carbini -
jim bell