NP-Complete Algorithms

Explanation

Non-deterministic Turing Machine in Polynomial time

https://www.geeksforgeeks.org/np-completeness-set-1/

NP-Hard

  • Cannot be completed by a computer

NP-Complete

  • 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

NP

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

P

  • Can be solved by deterministic turing machine in poly time

Notes

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

Set-covering

O(2n) to calculate all the subsets

np-complete

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
final_stations.add(best_station)

Java

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);
                covered.retainAll(station.getValue());

                if (covered.size() > statesCovered.size()) {
                    bestStation = station.getKey();
                    statesCovered = covered;
                }
                statesNeeded.removeIf(statesCovered::contains);

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

Traveling salesman

O(n!)

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

np-complete

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

Knapsack

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]