[MINI] Exponential Time Algorithms
Data Skeptic24 Nov 2017

[MINI] Exponential Time Algorithms

In this episode we discuss the complexity class of EXP-Time which contains algorithms which require $O(2^{p(n)})$ time to run. In other words, the worst case runtime is exponential in some polynomial of the input size. Problems in this class are even more difficult than problems in NP since you can't even verify a solution in polynomial time.

We mostly discuss Generalized Chess as an intuitive example of a problem in EXP-Time. Another well-known problem is determining if a given algorithm will halt in k steps. 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.

Episoder(588)

Populært innen Vitenskap

fastlegen
rekommandert
jss
rss-rekommandert
tingenes-tilstand
sinnsyn
rss-nysgjerrige-norge
dekodet-2
villmarksliv
forskningno
doktor-fives-podcast
rss-paradigmepodden
vett-og-vitenskap-med-gaute-einevoll
tomprat-med-gunnar-tjomlid
psykopoden
abid-nadia-skyld-og-skam
tidlose-historier
pod-britannia
katastrofe-i-hjernen
diagnose