3 ms·
Why not? In addition, he could demostrate that any given NP problem can be solved in O(N^2) time complexity.
by faragon 17y ago
Why not? In addition, he could demostrate that any given NP problem can be solved in O(N^2) time complexity.
- eru 17y agoI guess that'll be impossible.
- jrp 17y agoHaha, good but http://en.wikipedia.org/wiki/Time_hierarchy_theorem http://en.wikipedia.org/wiki/Time_hierarchy_theorem says no.
- tjr 17y agoAs if that could stop Knuth...
- faragon 17y agoBut what if you: 1) Create a list of pairs for the N nodes, N^2/2 elements: O(N^2). This point complexity could be ignored, as an initialization phase, as precomputed data for next step. In addition, many lists of hamiltonian subpaths could be added for trading memory for time complexity (not big deal, just linear speedup). 2) Dynamic-size (hamiltonian path subset) algebraic mergesort (avoiding evaluation, in order to avoid O(N!)): O(NlogN), or maybe O(N^2), or O(N^2logN) That could give you time complexity between O(N^2) and O(N^2logN). I tried something for the point (2), but obviously I had no success on compensating the combinatorial explosion with simplification/remapping. Possible or not, it is neverending and cheap fun.