Hardness of NP

In computer science, NP-hard problems are widely believed to be intractable, not because they have been proved so, but on the empirical evidence of no one having found a fast algorithm for any of them in over half a century of trying.  But the concepts of  NP-hardness and NP-completeness are themselves hard for newcomers to understand.   The current American Physical Society piece Unbearable Hardness of Physics makes a common mistake when it takes NP-hard problems to mean problems Not solvable in time Polynomial in the size of their input, rather than those to which all problems solvable in Nondeterministic Polynomial time are efficiently reducible.  Come to think of it, the letters N and P  also breed confusion in other fields, including our own, where  NPT is often taken to stand for Negative Partial Transpose, when it would be more correct to say Nonpositive Partial Transpose, admittedly a tiny imprecision compared to the confusion surrounding what NP means.

One Reply to “Hardness of NP”

Leave a Reply

Your email address will not be published. Required fields are marked *