Hacker News

points by vanderZwan 3 days ago | 0 comments

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.

[–] 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.