4 ms·
P vs NP is not an "in practical terms" question. It is a theoretical question with theoretical definitions of theoretical terms, including "efficient", which di
by johnday 3y ago
P vs NP is not an "in practical terms" question. It is a theoretical question with theoretical definitions of theoretical terms, including "efficient", which directly corresponds to the class P by definition.
- markusde 3y agoOk. When I say efficient, I mean "produces efficient code on near-term hardware". I understand that complexity theorists have a different definition of "efficient"-- they also have a different definition of "important" too.
- tsimionescu 3y agoThe question being asked was "what would proving P=NP mean for us in practical terms". The fact that mathematicians call all polynomial-time algorithms efficient is irrelevant to this question.
- johnday 3y ago> The question being asked Where was that question asked?
- tsimionescu 3y agoIt wasn't exactly a question, but the thread started by discussing practical implications: > That said, there is definitely potential practical implications for this. Even if it means we can know np problems do not have efficient solutions [emphasis mine] So, this was about efficiency in the practical sense, not some largely useless definition of efficiency by which galactic algorithms are "efficient".