Undecidable Problems, Graphs + Heuristics

Overview

This lesson explores three key concepts in computer science:

Decidable vs. Undecidable Problems - Understanding what problems computers can and cannot solve
Graph Theory - A powerful way to represent relationships between objects
Heuristics - Practical approaches for solving complex problems

Collegeboard Definitions (Big Ideas)

Code	Concept	Definition
AAP-4.B.1	Decidable Problem	A decision problem for which an algorithm exists that produces a correct yes-or-no answer for all possible inputs.
AAP-4.B.2	Undecidable Problem	A decision problem for which no algorithm can be constructed that always provides a correct yes-or-no answer for all inputs.
AAP-4.B.3	Partial Solutions	For some undecidable problems, certain instances can be solved algorithmically, but no single algorithm solves all instances correctly.

Decidable Problems

These are problems where an algorithm can definitively provide a correct answer for all possible inputs in finite time.

Examples:

Is a number even?
Is a string a palindrome?
Does a list contain a specific value?

# Decidable problem: Is a number even?
def is_even(num):
    return num % 2 == 0

# Decidable problem: Is a string a palindrome?
def is_palindrome(s):
    return s == s[::-1]

Undecidable Problems

These are problems for which no algorithm can be constructed that always gives a correct answer for all possible inputs.

The most famous example: The Halting Problem

Halting Problem Simulator

Explore this interactive simulator to better understand the Halting Problem and why it is undecidable.

“Given a computer program and an input, will the program eventually halt (terminate) or will it run forever?”

Why is it undecidable? We can prove by contradiction that no algorithm can solve this for all possible programs and inputs.

The Paradoxical Proof

Imagine we have a magical function will_halt(program, input) that can predict if any program will halt on any input:

def will_halt(program, input):
    # Magically determines if program halts on input
    # Returns True if it halts
    # Returns False if it runs forever
    ...

# Now, let's create a paradoxical program:
def paradox():
    if will_halt(paradox, None):
        while True:  # Run forever
            pass
    else:
        return  # Halt immediately

The contradiction:

If will_halt(paradox, None) returns True, then paradox() will run forever (contradiction!)
If will_halt(paradox, None) returns False, then paradox() will halt immediately (contradiction!)

Therefore, the function will_halt cannot exist for all programs.

Partial Solutions (AAP-4.B.3)

Even though some problems are undecidable in general, we can often:

Solve them for specific types of inputs
Create approximate solutions
Set practical constraints (like time limits)

Graph Theory

Graphs are mathematical structures used to model relationships between objects.

Basic Components

Vertices (nodes): Objects in the graph
Edges: Connections between objects

Types of Graphs

Directed vs. Undirected
- In directed graphs, edges have a direction
- In undirected graphs, edges have no direction

Weighted vs. Unweighted
- In weighted graphs, edges have values (weights)
- In unweighted graphs, all edges are equal

Connected vs. Disconnected
- In connected graphs, there is a path between every pair of vertices
- In disconnected graphs, some vertices cannot be reached from others

Graph Representations

1. Adjacency Matrix

A 2D array where element [i][j] indicates if there is an edge from vertex i to vertex j.

For this graph:
    A --- B
   /|     |
  / |     |
 C  |     D
  \ |    /
   \|   /
    E---

Adjacency Matrix:
  | A | B | C | D | E |
--+---+---+---+---+---+
A | 0 | 1 | 1 | 0 | 1 |
--+---+---+---+---+---+
B | 1 | 0 | 0 | 1 | 0 |
--+---+---+---+---+---+
C | 1 | 0 | 0 | 0 | 1 |
--+---+---+---+---+---+
D | 0 | 1 | 0 | 0 | 1 |
--+---+---+---+---+---+
E | 1 | 0 | 1 | 1 | 0 |

2. Adjacency List

A collection of lists, where each list contains the neighbors of a vertex.

# For the same graph:
graph = {
    'A': ['B', 'C', 'E'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B', 'E'],
    'E': ['A', 'C', 'D']
}

Graph Traversal Algorithms

Breadth-First Search (BFS)

Explores all neighbors at the current depth before moving to nodes at the next depth
Uses a queue data structure
Good for finding shortest paths in unweighted graphs

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Using our example graph
bfs(graph, 'A')  # Output: A B C E D

Depth-First Search (DFS)

Explores as far as possible along each branch before backtracking
Uses a stack data structure (or recursion)
Good for maze solving, topological sorting, etc.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=" ")
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Using our example graph
dfs(graph, 'A')  # Output: A B D E C

Heuristics

A heuristic is a problem-solving approach that employs a practical method that may not be perfect but is sufficient for reaching an immediate goal.

What are Heuristics?

“Rules of thumb” or educated guesses
Practical approaches when finding an optimal solution is impractical
Often used for:
- Undecidable problems
- NP-hard problems
- Time-constrained scenarios

Real-World Example: The Traveling Salesperson Problem (TSP)

Problem: Find the shortest possible route that visits each city exactly once and returns to the origin city.

Challenge: For n cities, there are (n-1)!/2 possible routes. With just 20 cities, that’s over 60 quadrillion routes!

Solution: Use heuristics like:

1. Nearest Neighbor Algorithm

Start at a random city
Visit the nearest unvisited city
Repeat until all cities are visited
Return to the starting city

Interactive TSP Visualization

def nearest_neighbor_tsp(distances, start=0):
    n = len(distances)
    unvisited = set(range(n))
    unvisited.remove(start)
    tour = [start]
    current = start
    total_distance = 0
    
    while unvisited:
        nearest = min(unvisited, key=lambda city: distances[current][city])
        total_distance += distances[current][nearest]
        current = nearest
        tour.append(current)
        unvisited.remove(current)
    
    # Return to start
    total_distance += distances[current][start]
    tour.append(start)
    
    return tour, total_distance

Example:

For a 4-city problem with the following distances:

City	A	B	C	D
A	0	10	15	20
B	10	0	35	25
C	15	35	0	30
D	20	25	30	0

Starting from city A:

Nearest to A is B (distance 10)
Nearest to B is A (already visited), then D (distance 25)
Nearest to D is A (already visited), then B (already visited), then C (distance 30)
Return to A (distance 15)

Total route: A → B → D → C → A Total distance: 10 + 25 + 30 + 15 = 80

Note: This may not be optimal! The optimal route could be A → C → D → B → A with distance 15 + 30 + 25 + 10 = 80 (in this case they happen to be the same, but often they’re not).

Other Heuristic Approaches

Greedy Algorithms
- Make locally optimal choices at each step
- May not lead to global optimum
- Example: Nearest neighbor for TSP
Local Search
- Start with a solution and iteratively improve it
- Example: 2-opt for TSP (swap two edges if it improves the solution)
Meta-heuristics
- Higher-level strategies that guide other heuristics
- Examples:
  - Genetic algorithms (inspired by natural selection)
  - Simulated annealing (inspired by metallurgy)
  - Ant colony optimization (inspired by ant behavior)

Case Study: Package Delivery Route Optimization

A delivery company needs to determine routes for delivering packages to 100+ locations daily.

Challenges:

Finding the optimal route is an NP-hard problem
Computing all possible routes (100+ factorial) would take longer than the universe has existed
Routes need to be computed quickly (in minutes, not years)

Solution: Heuristic Approaches

Clustering - Group nearby locations
Nearest Neighbor - Create initial routes
Local Search - Refine routes by swapping deliveries between routes

Result:

Not mathematically optimal, but practically efficient
Routes computed in minutes instead of centuries
Significant fuel and time savings

Connection Between These Concepts

Undecidable Problems and Heuristics
- When problems can’t be solved algorithmically for all cases, heuristics offer practical solutions
- Example: While the halting problem is undecidable, we can use heuristics like timeout mechanisms
Graphs and Heuristics
- Many graph problems (like TSP) are NP-hard
- Heuristics make these problems tractable
- Example: Using nearest neighbor for TSP instead of checking all permutations
Real-World Applications
- Package delivery (UPS, FedEx)
- Network routing (Internet packets)
- Resource allocation (CPU scheduling)
- GPS navigation systems

Practice Problems

Problem 1: Classify as Decidable or Undecidable

For each problem, determine if it’s decidable or undecidable:

“Is the sum of two integers greater than 100?”
“Will this Python program ever print ‘Hello World’?”
“Do two regular expressions generate the same language?”
“Is this number prime?”

Answers

1. Decidable - Simple arithmetic comparison
2. Undecidable - Related to the halting problem
3. Undecidable - Equivalence of regular expressions is undecidable
4. Decidable - Primality testing has known algorithms

Problem 2: Graph Traversal

For the following graph:

    A --- B
   /|     |
  / |     |
 C  |     D
  \ |    /
   \|   /
    E---

Write the adjacency list representation
Show the traversal order using BFS starting from node A
Show the traversal order using DFS starting from node A

Answers

1. Adjacency List: ```python graph = { 'A': ['B', 'C', 'E'], 'B': ['A', 'D'], 'C': ['A', 'E'], 'D': ['B', 'E'], 'E': ['A', 'C', 'D'] } ``` 2. BFS from A: A → B → C → E → D 3. DFS from A: A → B → D → E → C (may vary based on implementation)

Problem 3: TSP with Nearest Neighbor

Given these distances between cities:

City	A	B	C	D	E
A	0	12	19	8	15
B	12	0	10	18	5
C	19	10	0	6	14
D	8	18	6	0	9
E	15	5	14	9	0

Find a route using the Nearest Neighbor heuristic starting from city A
Calculate the total distance

Answer

Starting from A: 1. Nearest to A is D (distance 8) 2. Nearest to D is C (distance 6) 3. Nearest to C is B (distance 10) 4. Nearest to B is E (distance 5) 5. Return to A (distance 15) Route: A → D → C → B → E → A Total distance: 8 + 6 + 10 + 5 + 15 = 44

MCQ Review Question

Question: A company delivers packages by truck and would like to minimize the length of the route that each driver must travel to reach n delivery locations. The company is considering two different algorithms for determining delivery routes.

Algorithm I Generate all possible routes, compute their lengths, and then select the shortest possible route. This algorithm does not run in reasonable time.

Algorithm II Starting from an arbitrary delivery location, find the nearest unvisited delivery location. Continue creating the route by selecting the nearest unvisited location until all locations have been visited. This algorithm runs in time proportional to n².

Which of the following best describes Algorithm II?

Options:

A: Algorithm II attempts to use an algorithmic approach to solve an otherwise undecidable problem.
B: Algorithm II uses a heuristic approa ch to provide an approximate solution in reasonable time.
C: Algorithm II provides no improvement over algorithm I because neither algorithm runs in reasonable time.
D: Algorithm II requires a much faster computer in order to provide any improvement over algorithm I.

Answer

B: Algorithm II uses a heuristic approach to provide an approximate solution in reasonable time. Explanation: Algorithm II is implementing the Nearest Neighbor heuristic. While it may not find the optimal solution, it runs in polynomial time (O(n²)), which is considered reasonable, unlike Algorithm I which would take factorial time (O(n!)).

Which of the following best explains why it is not possible to use computers to solve every problem?

Responses
A Current computer processing capabilities cannot improve significantly.

B Large-scale problems require a crowdsourcing model, which is limited by the number of people available to work on the problem.

C The ability of a computer to solve a problem is limited by the bandwidth of the computer’s Internet connection.

D There exist some problems that cannot be solved using any algorithm.

Answer

D: There exist some problems that cannot be solved using any algorithm. Explanation: These are known as undecidable problems in computer science. No matter how powerful a computer is, or how advanced algorithms become, there are some problems (like the Halting Problem) that no algorithm can ever solve for all possible inputs.

Homework Assignment

Research and write a brief explanation of another undecidable problem not discussed in class
Implement the Nearest Neighbor algorithm for the TSP in a programming language of your choice
Find a real-world example where heuristics are used and explain why an exact solution isn’t practical
Complete the Kahoot quiz on these topics: [Link to quiz]

Undecidable Problems, Graphs + Heuristics

Overview

Collegeboard Definitions (Big Ideas)

Decidable Problems

Undecidable Problems

The Paradoxical Proof

Partial Solutions (AAP-4.B.3)

Graph Theory

Basic Components

Types of Graphs

Graph Representations

1. Adjacency Matrix

2. Adjacency List

Graph Traversal Algorithms

Breadth-First Search (BFS)

Depth-First Search (DFS)

Heuristics

What are Heuristics?

Real-World Example: The Traveling Salesperson Problem (TSP)

1. Nearest Neighbor Algorithm

Example:

Other Heuristic Approaches

Case Study: Package Delivery Route Optimization

Connection Between These Concepts

Practice Problems

Problem 1: Classify as Decidable or Undecidable

Problem 2: Graph Traversal

Problem 3: TSP with Nearest Neighbor

MCQ Review Question

Homework Assignment

Additional Resources