Poly and Expo Classes

Gregory M. Kapfhammer

November 10, 2025

Learning objectives

Learning Objectives for Theoretical Machines

• CS-204-1: Use both intuitive analysis and theoretical proof techniques to correctly distinguish between problems that are tractable, intractable, and uncomputable.
• CS-204-2: Correctly use one or more variants of the Turing machine (TM) abstraction to both describe and analyze the solution to a computational problem.
• CS-204-3: Correctly use one or more variants of the finite state machine (FSM) abstraction to describe and analyze the solution to a computational problem.
• CS-204-4: Use a formal proof technique to correctly classify a problem according to whether or not it is in the P, NP, NP-Hard, and/or NP-Complete complexity class(es).
• CS-204-5: Apply insights from theoretical proofs concerning the limits of either program feasibility or complexity to the implementation of both correct and efficient real-world Python programs.

Poly and Expo are two key complexity classes!

Poly and Expo help with learning objectives CS-204-1 and CS-204-4. We will formally define these two critical complexity classes and explore their boundary. One thing we will learn is that small changes to problem definitions can dramatically shift complexity. As proofgrammers, let’s explore the distinction between tractable and intractable problems with both formal definitions and Python code. Let’s dive into the details!

Vast gulf between growth rates

Growth rate comparison

• Insight: Wow, these growth rates differ dramatically!
• Insight: Polynomial growth is feasible, exponential is not!

Exponential versus polynomial

• Polynomial time: \(n\), \(n^2\), \(n^3\), \(n^{100}\) (i.e., broadly tractable)
• Exponential time: \(2^n\), \(3^n\), \(n!\) (i.e., intractable for large \(n\))
• Key insight: Polynomial is feasible, exponential is not
• Numerical Example: \(2^{100} \approx 10^{30}\) versus \(100^2 = 10,000\)
• Cryptography: Security relies on exponential-time attacks

• Polynomial-time problems are considered “efficiently computable”
• Exponential-time problems are generally “computationally impractical”
• The polynomial/exponential boundary demarcates tractability

Poly formalizes polynomial-time

• Poly: problems solvable in polynomial time
• Definition: program runs in \(O(n^k)\) for some constant \(k\)
• Examples: containsGAGA, multiply, and sortWords
• Key insight: polynomial growth is feasible for large inputs
• Tractable: Poly problems considered efficiently solvable

Poly captures tractable computation: algorithms with polynomial running time scale reasonably with input size. A problem in Poly can be solved efficiently, making it practical for real-world applications! Wait, can you think of any circumstance in which a Poly algorithm might not be practical?

Formal definition of Poly

Poly definition

• Assume we already know problem \(L\) is computable
• Computational problem \(L\) is in Poly if solvable in polynomial time with a computable method
• For some constant \(k\), program runs in \(O(n^k)\) time
• Proofgrammers often want polynomial-time algorithms!

Expo captures exponential-time

• Expo: problems solvable in exponential time
• Definition: program runs in \(O(2^{n^k})\) for some constant \(k\)
• Examples: all Poly problems, plus factor and MCopiesOfC
• Key insight: exponential growth is infeasible for large inputs
• Contains Poly: every polynomial-time problem is also in Expo

Expo includes intractable problems: algorithms with exponential running time become impractical as input grows. A problem in Expo but not Poly is considered computationally intractable! Wait, is there any case in which we would prefer an Expo over a Poly algorithm? Can you explain why?

Formal definition of Expo

Expo definition

• Assume we already know a problem \(L\) is computable
• Computational problem \(L\) is in Expo if it is computable and solvable in exponential time
• For polynomial function \(p(n)\), program runs in \(O(2^{p(n)})\) time
• Important: Poly \(\subseteq\) Expo since polynomial is faster!

Poly is a subset of Expo

Explore containment relationship

• Key relationship to note: Poly \(\subseteq\) Expo
• Every polynomial-time algorithm is also exponential-time
• Some books refer to Poly as FP (function polynomial)
• Key questions to ask:
  • What are the practical implications of this relationship?
  • What are the “hallmarks” of problems in these classes?
  • Can we “tweak” a problem to make it Poly instead of Expo?
  • Overall, what is the “boundary” between Poly and Expo?

Examples that contrast complexity

• All3Sets: generate all 3-element subsets (polynomial)
• AllSubsets: generate all subsets (exponential)
• ShortestPath: find shortest path in graph (polynomial)
• TSP: find shortest Hamilton cycle (exponential, currently)
• Insight: small problem changes yield dramatic complexity shifts!
• Question: ways to “tweak” problems to make them tractable?

Subtle distinctions matter: asking for “all 3-element subsets” versus “all subsets” changes complexity from polynomial to exponential. Also, “shortest path” versus “shortest Hamilton cycle” crosses the Poly/Expo boundary!

All3Sets or AllSubsets?

• All3Sets: given set \(S\), return all 3-element subsets
• AllSubsets: given set \(S\), return all subsets
• Counting: for \(n\) elements, \(\binom{n}{3}\) vs \(2^n\) subsets
• Complexity: \(O(n^3)\) vs \(O(2^n)\)
• Boundary: polynomial vs exponential growth!

Exponential explosion: with 10 elements, All3Sets generates 120 subsets while AllSubsets generates 1024. About the same, right? With 20 elements: 1140 vs over 1 million! The difference becomes astronomical quickly!

All3Sets problem definition

All3Sets specification

• Given set \(S\) with \(n\) elements, return all 3-element subsets
• Output formatted as set of sets with \(\binom{n}{3} = O(n^3)\) subsets

AllSubsets problem definition

AllSubsets specification

• Given set \(S\) with \(n\) elements, return all possible subsets
• Output contains \(2^n\) subsets, exponential growth in input size

Run all3Sets in Python

• Analysis: three nested loops, each iterates at most \(n\) times
• Time complexity: \(O(n^3)\) or cubic time, which means it is in Poly!

Run allSubsets in Python

• Analysis: doubles number of subsets for each element
• Time complexity: \(O(2^n)\) or exponential time, in Expo but not Poly!

Graph path problems

• ShortestPath: find shortest path between two vertices
• TSP: find shortest Hamilton cycle visiting all vertices
• Algorithms: Bellman-Ford \(O(n^2)\) vs brute force \(O(n!)\)
• Complexity: polynomial vs exponential (no known poly algorithm)
• Insight: adding “visit all vertices” constraint changes everything!

Hamilton cycle constraint is expensive: requiring a path to visit every vertex exactly once transforms a tractable problem into an intractable one. TSP is a famous problem in Expo with no known polynomial algorithm! At least, yet!

Visualize an example graph

• Find shortest Hamilton cycle in weighted graph
• Must visit all vertices exactly once and return to start

TSP problem definition

TSP problem specification

• Can you decode the meaning of a,b,3 or b,c,1?
• Focus on the connections between vertices and their weights
• Connects to the TSPPath and ShortestPath problems
• Practical applications: logistics, scheduling, DNA sequencing

TSPPath problem definition

TSPPath specification

• Goal: Find shortest path visiting all vertices exactly once
• Alarm: No known polynomial algorithm for the general case!
• Currently, we have a \(O(n!)\) brute-force search where \(n! \in O(2^{n^2})\)

ShortestPath problem definition

ShortestPath specification

• When there are positive weights, solved by Dijkstra’s algorithm
• This means that it is in \(O(n^2)\) time, which is polynomial!
• Aha, this means that ShortestPath is in Poly, while TSPPath is in Expo!

Compare path and cycle

Exploring complexity class membership that is “obvious”

Using a similar graph data structure, two algorithms have vastly different complexity!

• ShortestPath: use Dijkstra or Bellman-Ford algorithm at \(O(n^2)\)
• TSP: no known polynomial algorithm, requires exponential search
• Small change in problem specification, huge complexity difference!

The boundary between Poly and Expo

• Subtle difference: small problem changes really alter complexity
• All3Sets versus AllSubsets: fixed size versus all sizes
• ShortestPath versus TSP: any path versus Hamilton cycle
• Key lesson: problem constraints matter enormously
• Proofgrammer skill: recognize when constraints push problems across boundary and try to “reel them back”!

Understanding the Poly/Expo boundary is crucial: as proofgrammers, we must first prove a problem computable and then recognize which problem variations are tractable and which are not. This guides algorithm design and problem formulation, with small “tweaks” changing tractability!

Problems in Expo but not Poly

• Open question: are there problems provably in Expo but not Poly?
• Difficulty: proving lower bounds is extremely hard
• HaltEx: artificial problem in Expo but not Poly
  • Given program \(P\) and input \(I\), simulate \(P\) on \(I\) for \(2^n\) steps
  • Requires at most an exponential nubmer of steps
  • This shows that Expo contains problems not in Poly
• Constructed: designed specifically to require exponential time

Proving separations is difficult: while we believe many problems require exponential time, rigorous proof is challenging, not all lower bounds known!

Why study Poly class?

• Tractability: Poly problems generally feasible in practice
• Model independence: Poly invariant across computational models
• Foundation: leads to NP-completeness theory
• Structure: polynomial algorithms have special properties
• Caveat: not all Poly algorithms practical (e.g., \(O(n^{100})\))!

Poly is the gold standard for efficiency: while not perfect (i.e., some polynomial algorithms are slow), Poly captures the essence of tractable computation. It’s the foundation for understanding computational limits!

Poly provides model independence

• Different models: Turing machines, Python, Java, C++
• Polynomial equivalence: models simulate each other with “polynomial overhead”, so Python as an “API” for a TM
• Robust definition: Poly remains consistent across models
• Exception: quantum computers may break this equivalence
• Insight: Poly is a fundamental complexity class!

Model independence is powerful: whether we analyze algorithms on Turing machines, Python programs, or real computers, Poly remains the same class. This mathematical robustness makes it the right abstraction for tractability!

Key insights for proofgrammers

• Poly and Expo: fundamental complexity classes
• Boundary matters: small problem changes shift complexity
• Tractability: Poly captures efficiently solvable problems
• Open questions: many problems’ complexity unknown
• Proofgrammer skill: recognize complexity boundaries
• Foundation: sets the stage for the “P versus NP” question!

Understanding Poly and Expo is essential: these complexity classes help proofgrammers reason about computational feasibility and guide algorithm design. Later, we’ll explore NP and the famous “P versus NP” question!