[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.

Det här avsnittet är hämtat från ett öppet RSS-flöde och publiceras inte av Podme. Det kan innehålla reklam.

Avsnitt(601)

Practicing and Communicating Data Science with Jeff Stanton

Practicing and Communicating Data Science with Jeff Stanton

Jeff Stanton joins me in this episode to discuss his book An Introduction to Data Science, and some of the unique challenges and issues faced by someone doing applied data science. A challenge to any ...

24 Okt 201436min

[MINI] The T-Test

[MINI] The T-Test

The t-test is this week's mini-episode topic. The t-test is a statistical testing procedure used to determine if the mean of two datasets differs by a statistically significant amount. We discuss how ...

17 Okt 201417min

Data Myths with Karl Mamer

Data Myths with Karl Mamer

This week I'm joined by Karl Mamer to discuss the data behind three well known urban legends. Did a large blackout in New York and surrounding areas result in a baby boom nine months later? Do sublimi...

10 Okt 201448min

Contest Announcement

Contest Announcement

The Data Skeptic Podcast is launching a contest- not one of chance, but one of skill. Listeners are encouraged to put their data science skills to good use, or if all else fails, guess! The contest w...

8 Okt 201412min

[MINI] Selection Bias

[MINI] Selection Bias

A discussion about conducting US presidential election polls helps frame a converation about selection bias.

3 Okt 201414min

[MINI] Confidence Intervals

[MINI] Confidence Intervals

Commute times and BBQ invites help frame a discussion about the statistical concept of confidence intervals.

26 Sep 201411min

[MINI] Value of Information

[MINI] Value of Information

A discussion about getting ready in the morning, negotiating a used car purchase, and selecting the best AirBnB place to stay at help frame a conversation about the decision theoretic principal known ...

19 Sep 201414min

Game Science Dice with Louis Zocchi

Game Science Dice with Louis Zocchi

In this bonus episode, guest Louis Zocchi discusses his background in the gaming industry, specifically, how he became a manufacturer of dice designed to produce statistically uniform outcomes.  Duri...

17 Sep 201447min

Populärt inom Vetenskap

allt-du-velat-veta
dumma-manniskor
p3-dystopia
rss-ufobortom-rimligt-tvivel
ufo-sverige
kapitalet-en-podd-om-ekonomi
sexet
medicinvetarna
svd-nyhetsartiklar
rss-vetenskapsradion
hacka-livet
rss-vetenskapsradion-2
paranormalt-med-caroline-giertz
det-morka-psyket
ufo-sverige-2
rss-spraket
halsorevolutionen
rss-klotet
dumforklarat
ideer-som-forandrar-varlden