## Tackling Hard Problems

#### Andy Novocin

## Math Problem of day

### Suppose you have a "pattern" matrix with each entry as either 0 or non-zero.

### What can you say about the minimum rank of this matrix over all possible entry values?

## Interview Question

### Delayed until mid-lecture!

## HW twiddling

### Final Homework cancelled next one pushed back.

### Only 5 now.

## Six classes left

### I want to cover:

- A large set of "Hard" problems
- Brute Force Techniques
- Meta-Heuristics (Genetic/evolutionary, simulated annealing, Branch and Bound, etc.)
- Dynamic Algorithms
- P vs NP vs NP-Complete vs NP-Hard
- Problem reductions
- Proofs of hardness
- Coping methods (approximation, corner cases, heuristics)

## Some classical hard problems

## Satisfiability (SAT)

### Given a set of boolean variables \(U = \{u_1, \ldots, u_n \}\)

### Also a set of clauses \(C = \{c_1, \ldots, c_m \}\).

### Is there an assignment of the \(u_i\) such that each \(c_j\) is True.

#### A clause \(c_j\) is a set of variables from \(U \cup \bar{U}\) joined by \( \lor \).

#### For instance \(c_j = \bar{u}_1 \lor u_2 \lor \bar{u}_4 \lor u_5 \).

## ICUP SAT-style

## Simple version of NP

### P, NP, NP-Complete, NP-Hard are all sets of problems (not algorithms).

### P is the set of all problems which, in the worst case, can be resolved in polynomial time.

### NP is the set of all problems which, given a potential answer, can be verified in polynomial time.

### NP-Hard is the set of all problems which can be used to solve any NP problem.

### NP-Complete is the NP-hard problems that are also NP (can be quickly verified).

## SAT is a big deal

### In 1971 Cook showed that SAT can be used to solve any problem which can be verified in polynomial time.

### It is the first NP-Complete problem, everyone else gets to do it the easy way.

### http://www.satcompetition.org/

### If you can solve SAT in polynomial time, you can solve a huge set of hard problems in polynomial time.

## 3-SAT

### Just like SAT but each clause is limited to 3 variables.

#### (2-SAT is in P, 3-SAT is in NP-Complete).

## ICUP 3-SAT

## Note

### If I give you a solution to that problem, you can check it quickly.

## K-th Largest Subset

### If I give you a set of integers, find the \(k\)-th largest subset of that set.

#### If I give you a possible answer, how quickly can you verify it?

## Brute Force

### Before we start getting too clever. We have to know how to just force our way through a problem.

### If the problem involves finding the right subset then we can brute force up until about 20-40 items.

### If the problem involves finding the right permutation then we can brute force up until about 10-15.

### Recall the chart from earlier this semester.

## Backtracking: a framework

### We want to march our way through all possible answers of some problem.

### We can see this (very abstractly) as finding all appropriate arrays \([a_1, \ldots, a_n]\) where I can map that array to an appropriate answer.

### For instance a particular subset of an \(n\) element set can be seen as \([1,0,1,\ldots, 0,0,1]\) (in or out for each element).

### Another example, every permutation of \(\{1, 2, \ldots, n \}\) is naturally an array (i.e. \([3,5,1,2,4]\)).

## Backtracking Pseudo-Code

```
def backtrack(ans_so_far, data):
if is_valid(ans_so_far, data):
process_solution(ans_so_far, data)
else:
next_options = create_options(ans_so_far, data)
for option in next_options:
add_option(ans_so_far, option, data)
backtrack(ans_so_far, data)
remove_option(ans_so_far, option, data)
```

## How to use

### This framework builds an answer array as we go and has some key components

`ans_so_far`

is an ever changing rep of our answer`is_valid`

verifies the correct answer`create_options`

gives all possible next moves`add_option`

and`remove_option`

updates our data and answer`process_solution`

prints, logs, or whatever upon a good result