Are you familiar with asymptotic time complexity aka Big-O? That (and maybe the concept of a reduction) are the only challenging concepts required.
-
-
"class of complexity problems with optimal algorithmic solution in polynomial time" = any problem you can solve in O(n^k) for any k = P NP = problems you can _check if you solved correctly_ in O(n^k) but we dunno if there's a way to _solve_ them in O(n^k)
2 replies 0 retweets 3 likes -
Replying to @simpolism @danlistensto and
This is a very simplified explanation missing many minor points/expressing things slightly incorrectly from an academic perspective, but this is the main gist.
2 replies 0 retweets 1 like -
Replying to @simpolism @danlistensto and
The thing about Traveling Salesman: it's solvable in O(2^n) (exponential time), we can check a solution in O(n^k) (polynomial time), but we don't know whether we can _solve it_ in O(n^k). If we can, P=NP.
1 reply 0 retweets 2 likes -
My planet is not serving pages right now >.< Once more into the breach....
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.