NP-Complete Algorithms


Non-deterministic Turing Machine in Polynomial time


  • Cannot be completed by a computer


  • No polynomial time solution discovered
  • No proof that poly time solution doesn’t exist
  • if any one of the NP complete problems can be solved in polynomial time, then all of them can be solved
  • Any given solution for NP-complete problems can be verified quickly, but there is no efficient known solution


  • Can be solved by non deterministic turing machine in poly time


  • Can be solved by deterministic turing machine in poly time


No fast algorithmic solution

Have to use approximation algorithms. Approximation algorithms are judged by:

  • How fast they are
  • How close they are to the optimal solution

there’s no easy way to tell if the problem you’re working on is NP-complete. Here are some giveaways:

  • Your algorithm runs quickly with a handful of items but really slows down with more items.
  • “All combinations of X” usually point to an NP-complete problem.
  • Do you have to calculate “every possible version” of X because you can’t break it down into smaller sub-problems? Might be NP-complete.
  • If your problem involves a sequence (such as a sequence of cities, like traveling salesperson), and it’s hard to solve, it might be NP-complete.
  • If your problem involves a set (like a set of radio stations) and it’s hard to solve, it might be NP-complete.
  • Can you restate your problem as the set-covering problem or the traveling-salesperson problem? Then your problem is definitely NP-complete.

Greedy algorithms

Greedy algorithms optimize locally, hoping to end up with a global optimum.

Greedy algorithms are easy to write and fast to run, so they make good approximation algorithms.

dijkstras and breadth-first search are greedy algorithms


O(2n) to calculate all the subsets


Approximate solution in python

while states_needed:
    best_station = None
    states_covered = set()
    for station, states in stations.items():
        covered = states_needed & states
        if len(covered) > len(states_covered):
            best_station = station
            states_covered = covered
states_needed -= states_covered


import java.util.*;

public class SetCovering {

    public static void main(String[] args) {
        Set<String> statesNeeded = new HashSet(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az"));
        Map<String, Set<String>> stations = new LinkedHashMap<>();

        stations.put("kone", new HashSet<>(Arrays.asList("id", "nv", "ut")));
        stations.put("ktwo", new HashSet<>(Arrays.asList("wa", "id", "mt")));
        stations.put("kthree", new HashSet<>(Arrays.asList("or", "nv", "ca")));
        stations.put("kfour", new HashSet<>(Arrays.asList("nv", "ut")));
        stations.put("kfive", new HashSet<>(Arrays.asList("ca", "az")));

        Set<String> finalStations = new HashSet<String>();
        while (!statesNeeded.isEmpty()) {
            String bestStation = null;
            Set<String> statesCovered = new HashSet<>();

            for (Map.Entry<String, Set<String>> station : stations.entrySet()) {
                Set<String> covered = new HashSet<>(statesNeeded);

                if (covered.size() > statesCovered.size()) {
                    bestStation = station.getKey();
                    statesCovered = covered;

                if (bestStation != null) {
        System.out.println(finalStations); // [ktwo, kone, kthree, kfive]

Traveling salesman


running time is same whether you provide a starting city or not


just pick the closest city every time to get the approximate solution


Try every set until you get the most money: O(2n)

put in sack in order of cost for approximate solution

Formula to fill grid:

cell[row][column] = previous max for that column [row-1][column] VS value of current item + cell[row-1][column-current item weight]