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

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

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

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