When Problems Are Inherently Hard

Concepts covered: Dynamic Programming

Everything we have studied so far is about making problems faster. But some problems resist speed. No matter how clever your algorithm is, no matter how many machines you throw at it, certain problems are fundamentally, mathematically, provably hard. Understanding which problems fall into this category is one of the most practically valuable things in computer science, because it saves you from wasting weeks trying to build something that cannot be built.

The Two Sides of Every Problem

Consider a jigsaw puzzle. Solving it (finding where each piece goes) is hard. It requires trying many combinations, backtracking when pieces do not fit, and potentially exploring a vast number of arrangements. But checking a completed puzzle is easy. You just verify that every piece fits with its neighbors. This asymmetry between "hard to solve" and "easy to check" is the foundation of computational complexity theory.

Computer scientists formalized this into two groups. The group called P contains problems you can both solve and check quickly. Sorting is in P: you can sort a list in O(n log n) and verify it is sorted in O(n). The group called NP contains problems you can check quickly, even if solving them might be slow. The jigsaw puzzle is in NP: checking a solution is fast, but finding one may require exploring an enormous number of possibilities.

What Makes a Problem "Hard"?

The problems in NP that appear hardest are called NP-complete. They share a remarkable property: if anyone ever finds a fast algorithm for even one of them, that algorithm can be transformed to solve every NP-complete problem quickly. Thousands of problems from scheduling to routing to circuit design to gene sequencing have been proven NP-complete. The fact that no one has found a fast algorithm for any of them in over 50 years of trying is strong evidence that these problems are genuinely hard.

The most famous open question in computer science is whether P equals NP. In plain language: "Is every problem whose answer is easy to check also easy to solve?" Most experts believe the answer is no, but no one has proven it. Whoever does will win a $1 million prize from the Clay Mathematics Institute.

Hard Problems You Actually Encounter

You might think NP-complete problems are abstract puzzles with no practical relevance. In reality, data engineers bump into them regularly, often without realizing it.

Why it matters: evaluating every possible combination of N index columns requires 2^N queries. Adding one column doubles the work. This is why multi-column index selection is solved with heuristics, not exhaustive search.

Living with Hard Problems

Proving a problem is NP-hard does not mean giving up. It means adjusting your expectations. Instead of searching for a perfect solution, you use strategies that find a "good enough" solution quickly. In practice, these strategies work remarkably well.

# Approximation vs exact: partition balancing
import random

random.seed(42)
table_sizes = [random.randint(100, 10000) for _ in range(20)]
num_partitions = 4

def greedy_balance(sizes, k):
    """Greedy: assign each table to the lightest partition.
    Sort biggest-first for better results. O(n log n)."""
    sizes_sorted = sorted(sizes, reverse=True)
    partitions = [0] * k
    
    for size in sizes_sorted:
        lightest = partitions.index(min(partitions))
        partitions[lightest] += size
    
    return partitions

def naive_round_robin(sizes, k):
    """Round robin: just cycle through partitions. O(n)."""
    partitions = [0] * k
    for i, size in enumerate(sizes):
        partitions[i % k] += size
    
    return partitions

greedy_result = greedy_balance(table_sizes, num_partitions)
naive_result = naive_round_robin(table_sizes, num_partitions)
perfect = sum(table_sizes) / num_partitions

print(f"20 tables, sizes from 100 to 10,000")
print(f"Perfect balance would be {perfect:,.0f} per partition")
print(f"\nGreedy balance: {greedy_result}")
print(f"  Max: {max(greedy_result):,}  Min: {min(greedy_result):,}  Gap: {max(greedy_result)-min(greedy_result):,}")
print(f"\nNaive round-robin: {naive_result}")
print(f"  Max: {max(naive_result):,}  Min: {min(naive_result):,}  Gap: {max(naive_result)-min(naive_result):,}")
print(f"\nGreedy gets within {((max(greedy_result) / perfect) - 1) * 100:.1f}% of perfect.")
print(f"And it runs in O(n log n), not exponential time.")

Output:

20 tables, sizes from 100 to 10,000
Perfect balance would be 24,818 per partition

Greedy balance: [24895, 24832, 24800, 24745]
  Max: 24,895  Min: 24,745  Gap: 150

Naive round-robin: [26063, 26249, 22547, 24413]
  Max: 26,249  Min: 22,547  Gap: 3,702

Greedy gets within 0.3% of perfect.
And it runs in O(n log n), not exponential time.

The Explosion of Possibilities

Why are these problems so hard? Because the number of possible solutions explodes as the input grows. For scheduling 10 tasks, there are about 3.6 million possible orderings (10!). For 20 tasks, there are about 2.4 quintillion orderings (20!). No computer can check them all. The growth is not just fast; it is so fast that adding even one more task can multiply the search space by a huge factor.

# How fast does the search space grow?
import math

print("Items  | Possible arrangements | Time at 1B/sec")
print("-" * 55)

for n in [5, 10, 15, 20, 25]:
    arrangements = math.factorial(n)
    seconds = arrangements / 1_000_000_000
    
    if seconds < 1:
        time_str = f"{seconds*1000:.1f} ms"
    elif seconds < 60:
        time_str = f"{seconds:.1f} seconds"
    elif seconds < 3600:
        time_str = f"{seconds/60:.1f} minutes"
    elif seconds < 86400 * 365:
        time_str = f"{seconds/86400:.0f} days"
    else:
        time_str = f"{seconds/(86400*365):,.0f} years"
    
    print(f"  {n:>3}   | {arrangements:>25,} | {time_str}")

print(f"\nAt 25 items, even a billion checks per second")
print(f"would take {math.factorial(25)/(86400*365*1e9):,.0f} years.")
print(f"The universe is about 13,800,000,000 years old.")

Output:

Items  | Possible arrangements | Time at 1B/sec
-------------------------------------------------------
    5   |                   120 | 0.0 ms
   10   |             3,628,800 | 0.0 ms
   15   |     1,307,674,368,000 | 21.8 minutes
   20   | 2,432,902,008,176,640,000 | 77 years
   25   | 15,511,210,043,330,985,984,000,000 | 491,857,289,028 years

At 25 items, even a billion checks per second
would take 491,857,289,028 years.
The universe is about 13,800,000,000 years old.

This is why heuristics matter. The greedy algorithm in our partitioning example checked only 20 options (one per table) and got within 0.3% of perfect. The exact approach would need to check every possible assignment of 20 tables to 4 partitions, a number so large it is impractical to compute. Heuristics trade a tiny amount of solution quality for an enormous reduction in computation time. In data engineering, "close enough, fast" always beats "perfect, never finishes."

About this lesson

This section is part of the Complexity: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.