points by dingdongditchme 3 days ago | 0 comments
I believe this stems from an incomplete understanding of the problem space on my part (excuse the multiple puns); but, I am skeptical Knuth really said P=NP. There are so many mathemtical examples of equations that clearly show P≠NP. Computing in itself was originally formed from using iterative methods to solve hard problems. Least-squares methods, sin() cos(), traveling salesman, so many to list? To say P=NP for all problems seems like a fools errand to me.
[–] vanderZwan 3 days ago
[–] dingdongditchme 2 days ago
thanks for the quote. Reading through it is clear that my understanding of P=NP is not complete enough. I would have thought n*M is precisely not polynomial but exponential time.
[–] zahlman 2 days ago
The two asterisks here represent exponentiation.
…Oh, I see. The M here is a hypothesized constant, with n as the base. That's how polynomial time looks. Exponential time would have n in the exponent.
[–] Dylan16807 11 hours ago
Clearly show it how?
It's not enough for finding a solution to be slower than verifying, it has to be slower by a particular extreme amount, and that has to hold for the best possible solution.
Also, there's a set of problems called NP-hard that you can convert any other NP problem into. For P≠NP we have to make sure all of the problems that are NP-hard have that speed difference (including the overhead from doing that conversion).
[–] kscarlet 3 days ago
Do you understand what P and NP mean?
[–] dingdongditchme 2 days ago
I am not a computer scientist so my understanding is "incomplete". I thought it stood for polynomial and non-polynomial time. But i do mix them up here and there. What i have read time and time again is that: If P≠NP would mean some problems really are harder to solve than to check (which feels intuitive given working encryption exists and all the mathematical functions that I know and understand). For example checking the roots of polynomials is easier than finding them in the first place.
[–] Ohentis 2 days ago
From this comment it isn't clear if you previously thought it stood for polynomial and non-polynomial and have been corrected or if you still have this misconception, but just in case: it actually stands for polynomial and nondeterministic polynomial. P is a subset of NP, they aren't opposites. And yes most people intuit that they likely aren't equal.
[–] dingdongditchme 2 days ago
thank you for the clarification! Turns out I still have a few things to learn.
https://www.informit.com/articles/article.aspx?p=2213858&WT....
> Don Knuth: As you say, I've come to believe that P = N P, namely that there does exist an integer M and an algorithm that will solve every n-bit problem belonging to the class N P in n**M elementary steps.