NP-Completeness

Complexity Classes

Not all problems can be solved efficiently. Complexity theory classifies problems by how hard they are to solve:

The famous P vs NP question — does P = NP? — is the most important unsolved problem in computer science. If P = NP, every problem whose solution can be verified quickly could also be solved quickly.

Key NP-Complete Problems

Dealing with NP-Complete Problems

Since no polynomial-time algorithm is known for NP-complete problems, we use these strategies:

• Approximation algorithms — find a solution within a guaranteed factor of optimal (e.g., 2-approximation for TSP)
• Heuristics — fast algorithms that work well in practice but have no guarantee (e.g., greedy TSP)
• Parameterized algorithms — efficient when a parameter (like solution size k) is small
• Special cases — some NP-complete problems become polynomial for restricted inputs
• Randomized algorithms — probabilistic approaches that give correct answers with high probability

import java.util.Arrays;

public class TSP {

    static int n;
    static int[][] dist;
    static int[][] dp;  // dp[mask][i] = min cost to visit all cities in mask, ending at i

    // Held-Karp DP — O(n² × 2ⁿ) — much better than O(n!) brute force
    static int tspDP() {
        dp = new int[1 << n][n];
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
        dp[1][0] = 0;  // start at city 0, only city 0 visited (mask = 0001)

        for (int mask = 1; mask < (1 << n); mask++) {
            for (int u = 0; u < n; u++) {
                if ((mask & (1 << u)) == 0) continue;  // u not in mask
                for (int v = 0; v < n; v++) {
                    if ((mask & (1 << v)) != 0) continue;  // v already visited
                    int newMask = mask | (1 << v);
                    dp[newMask][v] = Math.min(dp[newMask][v], dp[mask][u] + dist[u][v]);
                }
            }
        }

        // Find minimum cost to return to city 0 after visiting all cities
        int fullMask = (1 << n) - 1;
        int minCost = Integer.MAX_VALUE;
        for (int u = 1; u < n; u++) {
            minCost = Math.min(minCost, dp[fullMask][u] + dist[u][0]);
        }
        return minCost;
    }

    public static void main(String[] args) {
        n = 4;
        dist = new int[][]{
            {0, 10, 15, 20},
            {10, 0, 35, 25},
            {15, 35, 0, 30},
            {20, 25, 30, 0}
        };

        System.out.println("Minimum TSP tour cost: " + tspDP());  // 80
        // Optimal tour: 0 → 1 → 3 → 2 → 0 = 10+25+30+15 = 80
    }
}

What is a Reduction?

To prove a problem B is NP-hard, we show that a known NP-hard problem A can be reduced to B in polynomial time. This means: if we could solve B efficiently, we could also solve A efficiently. Since A is NP-hard (no known polynomial solution), B must be at least as hard.

The first problem proven NP-complete was SAT (Boolean Satisfiability) by Stephen Cook in 1971 (Cook's Theorem). All other NP-complete problems were proven by reduction from SAT or from each other.

P vs NP — The Million Dollar Question

The P vs NP problem asks: Is every problem whose solution can be verified quickly also solvable quickly?

• If P = NP: Every NP problem has a polynomial-time algorithm. Cryptography would break (RSA, AES rely on hard problems). Huge implications for science, medicine, AI.
• If P ≠ NP (widely believed): NP-complete problems have no polynomial-time algorithm. Current cryptography remains secure.
• This is one of the Millennium Prize Problems — solving it earns $1,000,000 from the Clay Mathematics Institute.