3 ms·
“Not polynomial” is an easy trap to fall into (and one I have fallen into) but it’s really not correct. All polynomial-time problems are also NP problems (P=NP
by Skeime 3y ago
“Not polynomial” is an easy trap to fall into (and one I have fallen into) but it’s really not correct. All polynomial-time problems are also NP problems (P=NP is about whether the converse is true, and if P=NP, all problems in NP are actually polynomial-time). So even if talking to a layman, saying that NP is non-polynomial is really missing the point of the question.