# 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

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
``````

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) {
}
}
}
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]`