1. Undecidable Problem: Post Correspondence Problem (PCP)

The Post Correspondence Problem is an undecidable problem introduced by Emil Post in 1946. Given two lists of strings over some alphabet (say, List A and List B), the goal is to determine whether there exists a sequence of indices that, when used to concatenate corresponding strings from both lists, results in the same string.

Example: A = [“ab”, “a”], B = [“a”, “ba”] Try index sequence: [1, 2] A[1]+A[2] = “ab”+“a” = “aba” B[1]+B[2] = “a”+“ba” = “aba” → Match found.

However, the general case of finding such a sequence is undecidable—there’s no algorithm that solves it for all possible inputs. This problem is important in computability theory and reductions.

2. Nearest Neighbor Algorithm for the Traveling Salesman Problem (TSP)

Here’s a simple Python implementation of the Nearest Neighbor heuristic:

import numpy as np

def nearest_neighbor_tsp(dist_matrix, start=0):
    n = len(dist_matrix)
    visited = [False] * n
    tour = [start]
    visited[start] = True
    current = start

    for _ in range(n - 1):
        next_city = np.argmin([dist_matrix[current][j] if not visited[j] else float('inf') for j in range(n)])
        tour.append(next_city)
        visited[next_city] = True
        current = next_city

    tour.append(start)  # Return to start
    return tour

# Example distance matrix
dist_matrix = [
    [0, 2, 9, 10],
    [1, 0, 6, 4],
    [15, 7, 0, 8],
    [6, 3, 12, 0]
]

print("Tour:", nearest_neighbor_tsp(dist_matrix))

3. Real-World Example of Heuristics: Google Maps Route Planning

Context: Google Maps often uses heuristics when suggesting driving routes between locations.

Why Not an Exact Solution? An exact algorithm for finding the absolute fastest route would need to consider:

  • Real-time traffic updates
  • Construction zones
  • Accidents
  • Traffic light timings
  • Turn restrictions

Given the size and dynamic nature of road networks, computing an exact solution in real-time is computationally expensive and often infeasible. Instead, Google uses heuristics like A* search with estimates based on traffic history and live data to give good-enough routes quickly.