[MINI] Exponential Time Algorithms

Data Skeptic · Intermediate ·⚡ Algorithms & Data Structures ·8y ago

Key Takeaways

The episode discusses EXP-Time complexity class, which includes algorithms requiring $O(2^{p(n)})$ time to run, and explores problems like Generalized Chess and halting problem variants.

Original Description

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.
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from Data Skeptic · Data Skeptic · 0 of 60

← Previous Next →
1 Data Skeptic book giveaway contest winner selection
Data Skeptic book giveaway contest winner selection
Data Skeptic
 2 OpenHouse - Front end and API overview
OpenHouse - Front end and API overview
Data Skeptic
 3 OpenHouse Crawling with AWS Lambda
OpenHouse Crawling with AWS Lambda
Data Skeptic
 4 [MINI] Logistic Regression on Audio Data
[MINI] Logistic Regression on Audio Data
Data Skeptic
 5 Data Provenance and Reproducibility with Pachyderm
Data Provenance and Reproducibility with Pachyderm
Data Skeptic
 6 [MINI] Primer on Deep Learning
[MINI] Primer on Deep Learning
Data Skeptic
 7 Big Data Tools and Trends
Big Data Tools and Trends
Data Skeptic
 8 [MINI] Automated Feature Engineering
[MINI] Automated Feature Engineering
Data Skeptic
 9 The Data Refuge Project
The Data Refuge Project
Data Skeptic
 10 [MINI] The Perceptron
[MINI] The Perceptron
Data Skeptic
 11 [MINI] Feed Forward Neural Networks
[MINI] Feed Forward Neural Networks
Data Skeptic
 12 Data Science at Patreon
Data Science at Patreon
Data Skeptic
 13 [MINI] Backpropagation
[MINI] Backpropagation
Data Skeptic
 14 [MINI] GPU CPU
[MINI] GPU CPU
Data Skeptic
 15 OpenHouse
OpenHouse
Data Skeptic
 16 [MINI] Generative Adversarial Networks
[MINI] Generative Adversarial Networks
Data Skeptic
 17 [MINI] AdaBoost
[MINI] AdaBoost
Data Skeptic
 18 [MINI] The Bootstrap
[MINI] The Bootstrap
Data Skeptic
 19 [MINI] Dropout
[MINI] Dropout
Data Skeptic
 20 [MINI] Gini Coefficients
[MINI] Gini Coefficients
Data Skeptic
 21 [MINI] Random Forest
[MINI] Random Forest
Data Skeptic
 22 [MINI] Heteroskedasticity
[MINI] Heteroskedasticity
Data Skeptic
 23 [MINI] ANOVA
[MINI] ANOVA
Data Skeptic
 24 Urban Congestion
Urban Congestion
Data Skeptic
 25 [MINI] The CAP Theorem
[MINI] The CAP Theorem
Data Skeptic
 26 Unstructured Data for Finance
Unstructured Data for Finance
Data Skeptic
 27 Detecting Terrorists with Facial Recognition?
Detecting Terrorists with Facial Recognition?
Data Skeptic
 28 Predictive Models on Random Data
Predictive Models on Random Data
Data Skeptic
 29 [MINI] Entropy
[MINI] Entropy
Data Skeptic
 30 [MINI] F1 Score
[MINI] F1 Score
Data Skeptic
 31 Causal Impact
Causal Impact
Data Skeptic
 32 Machine Learning on Images with Noisy Human-centric Labels
Machine Learning on Images with Noisy Human-centric Labels
Data Skeptic
 33 The Library Problem
The Library Problem
Data Skeptic
 34 Stealing Models from the Cloud
Stealing Models from the Cloud
Data Skeptic
 35 Data Science at eHarmony
Data Science at eHarmony
Data Skeptic
 36 Multiple Comparisons and Conversion Optimization
Multiple Comparisons and Conversion Optimization
Data Skeptic
 37 Election Predictions
Election Predictions
Data Skeptic
 38 [MINI] Calculating Feature Importance
[MINI] Calculating Feature Importance
Data Skeptic
 39 MS Connect Conference
MS Connect Conference
Data Skeptic
 40 Music21
Music21
Data Skeptic
 41 The Police Data and the Data Driven Justice Initiatives
The Police Data and the Data Driven Justice Initiatives
Data Skeptic
 42 Studying Competition and Gender Through Chess
Studying Competition and Gender Through Chess
Data Skeptic
 43 [MINI] Goodhart's Law
[MINI] Goodhart's Law
Data Skeptic
 44 Trusting Machine Learning Models with LIME
Trusting Machine Learning Models with LIME
Data Skeptic
 45 [MINI] Leakage
[MINI] Leakage
Data Skeptic
 46 Predictive Policing
Predictive Policing
Data Skeptic
 47 Mutli-Agent Diverse Generative Adversarial Networks
Mutli-Agent Diverse Generative Adversarial Networks
Data Skeptic
 48 [MINI] Convolutional Neural Networks
[MINI] Convolutional Neural Networks
Data Skeptic
 49 Unsupervised Depth Perception
Unsupervised Depth Perception
Data Skeptic
 50 [MINI] Max-pooling
[MINI] Max-pooling
Data Skeptic
 51 MS Build 2017
MS Build 2017
Data Skeptic
 52 Activation Functions
Activation Functions
Data Skeptic
 53 Doctor AI
Doctor AI
Data Skeptic
 54 [MINI] The Vanishing Gradient
[MINI] The Vanishing Gradient
Data Skeptic
 55 CosmosDB
CosmosDB
Data Skeptic
 56 Estimating Sheep Pain with Facial Recognition
Estimating Sheep Pain with Facial Recognition
Data Skeptic
 57 [MINI] Conditional Independence
[MINI] Conditional Independence
Data Skeptic
 58 MINI: Bayesian Belief Networks
MINI: Bayesian Belief Networks
Data Skeptic
 59 Project Common Voice
Project Common Voice
Data Skeptic
 60 [MINI] Recurrent Neural Networks
[MINI] Recurrent Neural Networks
Data Skeptic

This episode introduces EXP-Time complexity class and its relation to NP, using Generalized Chess and halting problem as examples. It highlights the challenges of problems in EXP-Time, which are difficult to solve and verify.

Key Takeaways
  1. Understand the definition of EXP-Time complexity class
  2. Recognize problems that belong to EXP-Time, such as Generalized Chess
  3. Analyze the halting problem and its variants
  4. Compare EXP-Time to NP complexity class
💡 Problems in EXP-Time are particularly challenging because their worst-case runtime is exponential in some polynomial of the input size, making them difficult to solve and verify.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →