Date: Fri, 24 Nov 2017 16:00:00 +0000
<p class="p1"><span class="s1">In this episode we discuss the complexity class of EXP-Time which contains algorithms which require $O(2^{p(n)})$ time to run.<span class="Apple-converted-space"> </span> In other words, the worst case runtime is exponential in some polynomial of the input size.<span class="Apple-converted-space"> </span> Problems in this class are even more difficult than problems in NP since you can't even verify a solution in polynomial time.</span></p> <p class="p1"><span class="s1">We mostly discuss Generalized Chess as an intuitive example of a problem in EXP-Time.<span class="Apple-converted-space"> </span> Another well-known problem is determining if a given algorithm will halt in k steps.<span class="Apple-converted-space"> </span> That extra condition of restricting it to k steps makes this problem distinct from Turing's original definition of the halting problem which is known to be intractable.</span></p>
