Undecidable Problems, Graphs + Heuristics

Undecidable Problem: The Post Correspondence Problem (PCP) The Post Correspondence Problem is an undecidable problem in theoretical computer science. It involves determining whether, given two lists of strings over some alphabet, there exists a sequence of indices such that the corresponding strings from both lists, when concatenated in that order, produce the same string.

Example: Given:

  • List A: [“a”, “ab”]
  • List B: [“aa”, “b”]

Is there a sequence of indices (e.g., 1, 2) where: A[1] + A[2] == B[1] + B[2]`?

This problem is undecidable because there is no algorithm that can determine the answer for all possible inputs.

Nearest Neighbor Algorithm for TSP (Python Implementation)


def tsp_nearest_neighbor(graph, start=0):
    n = len(graph)
    visited = [False] * n
    path = [start]
    visited[start] = True
    total_cost = 0
    current = start

    for _ in range(n - 1):
        next_city = None
        min_dist = float('inf')
        for j in range(n):
            if not visited[j] and 0 < graph[current][j] < min_dist:
                min_dist = graph[current][j]
                next_city = j
        if next_city is not None:
            path.append(next_city)
            visited[next_city] = True
            total_cost += min_dist
            current = next_city

    total_cost += graph[current][start]  # Return to starting city
    path.append(start)
    return path, total_cost

# Example graph (symmetric TSP)
graph = [
    [0, 2, 9, 10],
    [1, 0, 6, 4],
    [15, 7, 0, 8],
    [6, 3, 12, 0]
]

route, cost = tsp_nearest_neighbor(graph)
print("Path:", route)
print("Total cost:", cost)

Real-World Use of Heuristics: Scheduling Airline Flights Problem: Scheduling planes, gates, and crew to thousands of flights each day.

Why Heuristics Are Used:

  • The number of combinations of flight schedules, available planes, and crews grows exponentially.
  • An exact solution would take too long to compute.
  • Heuristics (e.g., greedy algorithms, genetic algorithms) provide “good enough” solutions quickly, which is essential in a time-sensitive industry.