|
more like no one should expect np to be efficiently solvable, but it could be that there exists some monstrous, but still polynomial, bound for those problems (e.g. it turns out that satisfiability is solvable in time n^100), which would rather mean the end for the polynomial hierarchy as a way of separating these things than it would mean that np-complete problems can be efficiently solved
|
#
¿
Jun 5, 2017 11:51
|
|
|
|
| # ¿ May 14, 2024 12:14 |
|
|
it is a legit philosophical conundrum why all "natural" problems tend to either be np (or worse), or n^c for very small integers c. is the small exponents inherent in what we view as natural, or is it that there exists families of stronger algorithms which we have difficulty discovering by intuitive means? primality testing surprisingly being in p, with a running time of O(n^12) (later reduced to O(n^6) granted) is one of the odd ones out, but may be the first of something bigger (having only been figured out in 2002)
|
|
#
¿
Jun 5, 2017 13:57
|
|
|
LP0 ON FIRE posted:i don't know if i like the video.. he mentions sorting. checking sorting can be done in polynomial time, but actually sorting - isn't that np? ....well, if the ordering isn't required to be transitive i guess? but mostly no
|
|
#
¿
Jun 6, 2017 16:40
|
|
|
LP0 ON FIRE posted:thanks that is good info ah, i think i see what your confusion is: what we certainly know is that p np. for sorting any sorting algorithm will indeed also in effect check whether the list is sorted (since it has little choice but to make repeated comparisons). it is the case in general as well, but it gets into slight technicalities at that point as these are "decision problems" (i.e. only yes/no answers, no actual output) that is, in this informal sense, np is the set of problems where one can in polynomial time *recognize* that a given solution indeed is a solution, where p are the problems where one can in polynomial time *create* a solution (which *implies* being able to recognize it). so, if these are the same, p=np, then it is sufficient that solutions can be recognized, there exists some general way to (efficiently) rework the recognition of solutions into an algorithm for the construction of solutions (and, as this is in polynomial time this general way is more clever than just enumerating all possible solutions) it makes a fair difference to how one can phrase things that the problems are all yes/no problems, but in practical terms the above is largely correct the one reason i can see to think that p could equal np is in the assumptions of that "(efficiently)" above, since complexity theory started out assuming anything that can be done in polynomial time to be somewhat tractable, which has sort of worked out, with most polynomial time algorithms having polynomials like n^2 and n^3. however, it may be that p=np with the "general way" above adding some polynomial like n^1000, making it in practice no better than the dumb enumeration of solutions. in that case the discovery would mostly just kill off the idea that we can view polynomial time as a useful complexity class in itself, and future complexity work would have to be rebuilt with a more carefully restricted class standing in for the tractable
|
|
#
¿
Jun 8, 2017 09:03
|
|
|
see, this is the sort of nonsense which one gets around by having complexity classes defined exclusively by yes/no problems. not that the statement above makes much sense either way, but clearly one wants to separate between something being difficult to compute in a deeper sense, and something taking a long time to do because the output demanded is large
|
|
#
¿
Jun 12, 2017 10:55
|
|
|
|
| # ¿ May 14, 2024 12:14 |
|
|
things that are actually useful to code monkeys are worthless by association, may as well try asking about something cool and interesting, like complexity theory or philosophy
|
|
#
¿
Jun 12, 2017 21:08
|
|