Polytime Mapping Reductions

Gregory M. Kapfhammer

November 24, 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.

Review of key concepts

• Poly: Problems solvable in polynomial time \(O(n^k)\)
• PolyCheck/NPoly: Problems with polytime verification
• Equivalence: PolyCheck = NPoly (proven!)
• Open question: Is Poly \(\subset\) PolyCheck/NPoly?
• Need tools: How do we compare problem difficulty?

Polyreductions provide comparison tools: we need formal techniques to prove that one problem is “as hard as” another. This chapter introduces polynomial-time mapping reductions that let proofgrammers establish relationships between computational problems! Let’s dive in!

Polyreductions prove X is as easy as Y! Helpful!

Polynomial-time mapping reductions help with learning objectives CS-204-1 and CS-204-4. We will define a powerful technique for comparing problem difficulty. This technique lets us prove that if we can solve problem \(G\) efficiently, then we can also solve problem \(F\) efficiently. As proofgrammers, let’s explore how to establish formal relationships between computational problems!

Focus on decision problems

• Focus shift: Rest of course uses decision problems
• Previous definitions: PACKING, PARTITION were nondecision problems
• Now converted: All problems become decision problems, which can be done in a mechanical fashion, no generality loss from proof perspective
• Why?: Building to NP-completeness, only defined for decision problems
• Example: PARTITION returns yes or no, not the computed partition

Decision problems simplify theoretical analysis: by focusing on yes/no questions, we can more elegantly state and prove hardness results. This is a standard in complexity theory! The fundamental ideas remain the same!

Two reduction methods

• Two reduction types: Turing versus polynomial-time mapping reductions
• Key difference: Time constraints and number of oracle calls
• Turing reductions: Prove computability relationships, unlimited time
• Polyreductions: Prove efficiency relationships, polynomial time
• Why compare?: Understanding restrictions helps choose right tool

Polyreductions are more restrictive but more powerful for complexity: by requiring polynomial-time transformations, they preserve efficiency relationships. This makes them perfect for comparing problem difficulty in complexity theory!

Recall: Turing reductions

• Turing reduction: Solve problem \(F\) by calling \(G\) as a subroutine
• No time limit: Focus is not on transformation’s efficiency
• Used for: Proving computability relationships among problems

Turing reductions played a central role in creating the tree of uncomputable problems through a proof-by-contradiction technique. Now, we define a new reduction to help with computational complexity!

Polynomial-time mapping reductions

• Polyreduction: Transform \(F\) instance to \(G\) instance in polytime
• Call once: Only one call to \(G\), then transform result back
• Strict constraint: Transformation must run in polynomial time
• Purpose: Proving efficiency relationships between problems
• Reminder: We will often use the shortcut phrase “polyreduces” for the longer phrase “polynomial-time mapping reduces”

Differences between reduction types

• Time constraint: Polyreductions require polynomial-time transformation
• Mapping: Polyreductions map instances directly, preserving structure
• Efficiency: Polyreductions preserve polynomial-time solvability
• Purpose: Polyreductions compare complexity, not just computability

Polyreductions are more restrictive but more powerful: the polynomial-time constraint means that polyreductions reveal efficiency relationships, not just computability relationships! This makes them perfect for complexity theory! Can you see how this builds on the “reduction concept” and then extends it? Okay, let’s formally defintine polyreductions!

Formal definition of polyreduction

• Formal notation: \(F \leq_P G\) means “F polyreduces to G”
• Three conditions: Must verify all three for valid reduction
• Transformation function: Convert \(F\) instances to \(G\) instances
• Interpretation: If \(G\) is efficiently solvable, then \(F\) is also!
• Proof structure: Always verify pos→pos, neg→neg, polytime

Three conditions work together: they ensure that solving \(G\) efficiently lets us solve \(F\) efficiently. Proofgrammers must verify all three conditions in every proof!

Polyreduction definition

• Notation: \(F \leq_P G\) means “\(F\) polyreduces to \(G\)”
• Three conditions: pos→pos, neg→neg, and polytime transformation
• Transformation: Function \(C\) converts \(F\) instances to \(G\) instances
• Interpretation: If we can solve \(G\), we can solve \(F\) efficiently

Recall: PACKING problem

• Input: Weights \(w_1, w_2, \ldots, w_m\) and thresholds \(L\) and \(H\)
• Metaphor: Load packages into delivery truck with weight limits
• Question: Can we select subset with total weight between \(L\) and \(H\)?
• Example: Weights “12 4 6 24 4 16; 20; 27” → solution “4 6 16” (total = 26)
• In PolyCheck: Easy to verify a proposed packing, hard to find one

Quick PolyCheck reminder: A problem is in PolyCheck if we can verify a proposed solution in polynomial time, even if finding that solution might be hard. PACKING fits perfectly: given a subset, we just sum the weights and check if \(L \leq \text{sum} \leq H\) in \(O(n)\) time! How connects to PARTITION?

Recall: PARTITION problem

• Input: Just weights \(w_1, w_2, \ldots, w_m\) (no thresholds!)
• Goal: Split into two equal-weight subsets
• Question: Can we partition weights so each half has same total?
• Example: Weights “12 4 6 14 4 16” → solution “12 16” (total = 28) vs “4 6 14 4” (total = 28). Can you explain this example in detail?
• Relationship: PARTITION is PACKING where \(L = H = \frac{\text{total weight}}{2}\)

Both problems are in PolyCheck: checking a proposed solution is easy (just sum the weights), but finding a solution seems hard. This makes them perfect examples for polyreductions! Let’s polyreduce PARTITION to PACKING. Make sure to confirm the three key conditions as we go!

Polyreduce PARTITION to PACKING

• Transform: Convert PARTITION instance to PACKING instance
• Preserve structure: Positive instances map to positive instances
• Key insight: Both problems involve subset selection with constraints
• Verify: Check pos→pos, neg→neg, and polynomial time

Compare Turing and polyreductions

• Turing reductions: Multiple calls to \(G\), adaptive, no time bound
• Polyreductions: Transformation from \(F\) to \(G\), polynomial time
• Trade-off: Flexibility vs stronger guarantees
• Power comparison: Polyreductions reveal efficiency relationships
• Complexity theory: Polyreductions are the right tool

Restrictions create power: by limiting to polynomial time and single transformations, polyreductions give us exactly what we need for NP-completeness theory! We will soon explore the definition of NP-completeness using these tools!

Turing reduction flexibility

• No time bound: Calls can take arbitrary time
• Weaker result: Only proves computability relationship

Polyreduction constraints

• Time bounded: Transformation must be polynomial
• Stronger result: Proves efficiency relationship

Polyreductions are stricter but reveal more: the constraints mean that \(F \leq_P G\) tells us that \(F\) is “no harder” than \(G\) in terms of computational complexity! Hooray, this is exactly what we need for NP-completeness!

Proof technique for polyreductions

• Standard template: Same proof structure for all polyreductions
• Condition 1: Positive instances map to positive instances
• Condition 2: Negative instances map to negative instances
• Condition 3: Transformation runs in polynomial time
• Proof strategy: Describe transformation, verify all three

Follow this template every time: systematic verification of all three conditions ensures correctness. Proofgrammers should make this second nature!

Three conditions to verify

• Condition 1 (pos→pos): Every positive instance of \(F\) maps to a positive instance of \(G\)
• Condition 2 (neg→neg): Every negative instance of \(F\) maps to negative instance of \(G\)
• Condition 3 (polytime): The transformation \(C\) runs in polynomial time
• Key insight: Conditions 1 and 2 together ensure correctness
• Why polytime?: Ensures efficiency is preserved, which is critical for complexity

Follow this template for every polyreduction proof: (1) describe the transformation, (2) prove pos→pos, (3) prove neg→neg, (4) analyze running time. This systematic approach works for all polyreduction proofs!

• Next: Investigate graph problems with Hamilton cycles
• Then: Explore satisfiability problems: CircuitSAT, SAT, 3-SAT

Graph polyreductions with Hamilton cycles

• Hamilton cycles: Visit every vertex exactly once, return to start
• Two variants: Undirected (UHC) and directed (DHC) graphs
• Relationship: Are they equally hard?
• Goal: Show UHC \(\equiv_P\) DHC via bidirectional reductions
• Technique: Graph transformation gadgets

Hamilton cycle problems are NP-complete: understanding these reductions helps us see why seemingly different problems have the same computational difficulty! It turns out that UHC and DHC are equally hard! But, can we prove it?

Two important graph problems

• UHC: Does an undirected graph have a Hamilton cycle?
• DHC: Does a directed graph have a Hamilton cycle?
• Relationship: How do these problems compare?
  • Is it harder to solve the problem with directed or undirected edges?
  • Or, are directed and undirected edges equally hard to handle?
• Goal: Prove polyreduction relationships between them
• Key trick: Convert graph representations efficiently

Hamilton cycles are fundamental: many NP-complete problems involve finding paths or cycles that visit all vertices. Understanding these problems is crucial for complexity theory! This also influences practical methods!

Polyreduce UHC to DHC

• Key trick: Convert each undirected edge into two directed edges
• Exercise: Prove pos→pos, neg→neg, and polytime conditions
• Intuition: Undirected edge allows travel both ways

Polyreduce DHC to UHC

• Key trick: Convert each node into connected “triplets”
• Exercise: Prove pos→pos, neg→neg, and polytime conditions
• Intuition: Triplets enforce directional constraints

Triplet construction

• Each node becomes three: Node \(v\) becomes \(v_a\), \(v_b\), \(v_c\) (the triplet)
• Connect triplets: Add edges \(v_a\)-\(v_b\) and \(v_b\)-\(v_c\) (must traverse in order!)
• Directed edge becomes undirected: Edge \(v \to w\) becomes \(v_c\)-\(w_a\)
• Why this works: Hamilton cycle must visit each triplet as \(a \to b \to c\)
• Example: Directed cycle \(v_4 \to v_1\) becomes undirected \(v_{4a} \to v_{4b} \to v_{4c} \to v_{1a} \to v_{1b} \to v_{1c}\). See how this forces directionality?

• The triplet gadget is clever: it forces the undirected Hamilton cycle to “flow” through nodes in the same direction as the original directed graph! Any valid undirected cycle must enter at \(a\), pass through \(b\), and exit at \(c\).
• Bidirectional polyreductions: Since UHC \(\leq_P\) DHC and DHC \(\leq_P\) UHC, these problems are “equally hard”! This is called polyequivalence, which we’ll define!

Satisfiability problems are fundamental

• Boolean satisfiability: Can we make a formula or circuit output True?
• Three variants: CircuitSAT, SAT, and 3-SAT
• All polyequivalent: CircuitSAT \(\equiv_P\) SAT \(\equiv_P\) 3-SAT
• Central importance: Foundation for NP-completeness theory
• Real applications: Circuit design, verification, planning

SAT problems are everywhere: from verifying computer chips to scheduling problems to software testing. Understanding their equivalence helps us see the deep connections in computational complexity! Let’s start with some circuits!

CircuitSAT: Can a circuit output 1?

• Input: Boolean circuit with variables
• Question: Exists assignment making output = 1?
• Example: Circuit with AND, OR, NOT gates
• Applications: Circuit verification and design

SAT: Can a formula be satisfied?

• Input: Boolean formula in CNF (AND of ORs)
  • \(x_1\) through \(x_5\) are boolean variables
  • \(\neg x_2\) is the logical negation of \(x_2\)
  • \((x_1 \vee \neg x_2)\) is a logical OR clause
  • \(x_1 \wedge x_2\) combines clauses with logical AND
• Question: Exists assignment making formula True?
• CNF example: \((x_1 \vee \neg x_2) \wedge (x_2 \vee x_3)\)
• Restriction: CircuitSAT limited to formula structure

3-SAT: At most 3 literals per clause

• Input: CNF formula with \(\leq\) 3 literals per clause
• Question: Same as SAT, stricter format, are their differences?
• Surprising: No easier than general SAT!
• What comes next:
  • Make a total of four reduction claims
  • Prove polyequivalence among all three problems
  • Serve as a foundation for NP-completeness theory

Polyreductions for SATs

• Reduction claims:
  • CircuitSAT \(\leq_P\) SAT
  • SAT \(\leq_P\) CircuitSAT
  • 3-SAT \(\leq_P\) SAT
  • SAT \(\leq_P\) 3-SAT
• Polyequivalence: All three are equally hard!
• Key technique: Transform structure while preserving satisfiability

The reduction chain proves equivalence: each transformation preserves satisfiability in polynomial time, showing all three problems have the same fundamental difficulty! Wow, this is an impressive and powerful result!

CircuitSAT to SAT: Main idea

• Transform: Each gate becomes clauses enforcing its logic
• AND gate: \(z = x \wedge y\) becomes clauses about \(x, y, z\)
• OR gate: \(z = x \vee y\) becomes different clauses
• Result: Formula satisfiable iff circuit satisfiable

SAT to 3-SAT: Clause splitting

• Problem: Clause \((x_1 \vee x_2 \vee x_3 \vee x_4)\) too long
• Solution: Split using dummy variable \(z\)
• Result: \((x_1 \vee x_2 \vee z) \wedge (\neg z \vee x_3 \vee x_4)\)
• Preserves: Original satisfiable iff split version satisfiable

• Key insights:
  • Even though 3-SAT seems more restricted, it’s “just as hard” as SAT!
  • Next, we define polyequivalence to formalize “equal difficulty”!

Polyequivalence captures equal difficulty

• Polyequivalence: When problems \(F\) and \(G\) reduce to each other
• Equal difficulty: \(F \equiv_P G\) means same computational hardness
• Transitivity: Polyreductions compose to create equivalence classes
• Complexity classes: Groups of equally hard problems
• NP-completeness preview: Foundation for next chapter’s theory

Polyequivalence “partitions” problems into difficulty classes: if solving one problem in the class efficiently solves all problems in that class, then they form a natural unit of study. This creates the mathematical structure for NP-completeness!

Definition of polyequivalence

• Definition: \(F \equiv_P G\) if \(F \leq_P G\) and \(G \leq_P F\)
• Meaning: Problems are “equally hard”
• Examples: UHC \(\equiv_P\) DHC, CircuitSAT \(\equiv_P\) SAT \(\equiv_P\) 3-SAT
• Transitivity: If \(F \equiv_P G\) and \(G \leq_P H\), then \(F \equiv_P H\)

Polyequivalence creates complexity classes: problems that are polyequivalent have the same fundamental difficulty. This is the foundation for NP-completeness theory in the next chapter! Get ready for some fun!

Key insights for proofgrammers

• Polyreductions: Compare problem difficulty via transformations
• Three conditions: pos→pos, neg→neg, and polytime
• SAT problems: CircuitSAT, SAT, and 3-SAT are fundamental
• Polyequivalence: \(F \equiv_P G\) means equal difficulty
• Proof technique: Describe transformation, verify conditions
• Next chapter: NP-completeness builds on these ideas!

Polyreductions are the foundation of complexity theory: they let us prove that problems are equally hard and establish a hierarchy of difficulty. Next, we’ll use these tools to identify the “hardest” problems in NP!