Hacker News Reader

Comment by dingdongditchme | Hacker News Reader

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.

View on HN

See his answer to the seventeenth question in this interview:

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.

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.

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.

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).

Do you understand what P and NP mean?

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.

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.

thank you for the clarification! Turns out I still have a few things to learn.

Reply on news.ycombinator.com