People often wonder why anyone would care about polynomial/exponential time distinction. There is one reason that makes sense to me but it's not one I have seen mentioned in any book.
-
Show this thread
-
The idea that it is trying to capture the distinction between tractable and intractable problems simply doesn't make sense. Constant factors matter. Polynomial exponents matter.
1 reply 0 retweets 3 likesShow this thread -
The argument that for every practical problem solvable in poly time algorithms with small exponents have been found doesn't look very convincing given that it is also known there are problems solvable in O(n^1000) but not in O(n^999)
1 reply 0 retweets 1 likeShow this thread -
The distinction that is really being (approximately) captured is problems that don't require exhaustive search vs. those that do.
1 reply 1 retweet 5 likesShow this thread -
If there is a O(n^1000) algorithm for SAT - no matter how high the constants are - that algorithm is doing something that can't possibly resemble exhaustive search.
1 reply 0 retweets 3 likesShow this thread -
And because of the close relationship between SAT and computational universality that would mean there is a way to tell whether there is an input to an arbitrary Turing machine that accepts in N steps without just trying all the inputs.
4 replies 0 retweets 4 likesShow this thread -
Which is something that can't be computed if one allows for an arbitrary number of steps. And that would really be very interesting.
1 reply 0 retweets 3 likesShow this thread
This seems to motivate an exponential/sub-exponential time distinction, without motivating polynomial time.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.