Comment by m_mueller
1 day ago
wait, maybe this is the same problem....
with non-polynomial side being represented as the frontend programmer's constant need for more performance to do the same task...
1 day ago
wait, maybe this is the same problem....
with non-polynomial side being represented as the frontend programmer's constant need for more performance to do the same task...
worth mentioning that "NP" is not "non-polynomial" but "non-deterministic polynomial (time)". If NP was non-polynomial time then NP != P would be trivial (and in fact, P != EXP is known by the time hierarchy theorem).
Non-deterministic can be explained in several ways. One is in terms of a hypothetical "nondeterministic Turing machine" with certain non-physically realizable properties. The easier way is that a NP problem gets as input not only the problem instance x, but a "witness" w, that may depend on the problem instance. This witness generally makes the problem of deciding the problem instance straightforward (e.g. for SAT, x is the SAT instance, and w is a description of how to set the variables so that it is true).
I reckon I could tell you in polynomial time whether a div was vertically centered, not sure if I could write the CSS in polynomial time.