After almost 20 years, math problem falls

We say that an algorithm is in NP if checking a given solution can be done in polynomial time. For example, if the problem is to find a path that visits all the nodes of a graph (or cities on a salesman's route, or whatever) exactly once that's less than some distance k, you might have to try every possible route to find a solution, but given an answer, you can check it's distance and compare it to k very quickly.

NP-hard means (even more informally than the above) that the problem is "at least as hard as the hardest problem in NP". (Some problems in NP are easy; e.g., if you have an algorithm in P to find a solution to a problem, then you can obviously also check a given answer in polynomial time.)

It is not known whether or not all problems for which answers can be checked in polynomial time (NP) can also be solved in polynomial time (P).

They're saying that if P=NP, there does exist an algorithm in P that can decide the convexity of a degree 4 polynomial (even though they don't know what that algorithm is right now), and if P!=NP, then there doesn't.

(*Edit: The last paragraph is wrong:

I can't find that they've proven that the determining convexity is in NP, just that it's NP-hard and they didn't rule out it being in NP. (Recall that some NP-hard problems are not in NP; halting problem is one.)

So it's possible that that both P=NP and there's still no algorithm in P that can check convexity. But if P!=NP, that algorithm definitely doesn't exist.

Also, on closer reading, the relevant "size" of a problem that this paper is talking about (n) is the number of bits needed to represent the coefficients of the polynomial.)