## Proving Hardness

#### Andy Novocin

## Daily Challenge

### The longest common substring (not subsequence) of two strings X and Y is the longest string that appears as a run of consecutive letters in both strings. For example, the longest common substring of `photograph`

and `tomography`

is `ograph`

.

#### a) Let \(n = |X|\) and \(m = |Y|\). Give a \(\Theta(nm)\) dynamic programming algorithm for longest common substring based on the longest common subsequence/edit distance algorithm.

#### b) Give a simple \(\Theta(nm)\) algorithm that does not rely on dynamic programming.

## Interview Question Cont.

### You are given an array of \(n\) numbers, each of which may be positive, negative, or zero. Give an efficient algorithm to identify the index positions of \(i\) and \(j\) to maximize the sum of the \(i^{\textrm{th}}\) through \(j^{\textrm{th}}\) numbers.

## ACM Variant

### Given an array of 256 elements where each entry is -1 or 1 with equal probability. What is the expected value of the sum of a maximal contiguous sub-array?

## Learn to demonstrate

### Even for your own sake, saving time, or just plain knowing when you are chasing windmills.

## The role of NP

### Using Non-determinism in your analysis is stupidly powerful.

### Calling a problem solved if I can just verify a guess quickly...

### Playing the lotto == Winning the lotto

## NP exists

### The reason we have NP as a class, is so that we can corale a large set of "hard" problems.

### If we can "show" (\(P \neq NP\)) that we need a stupidly powerful assumption, then we've shown hardness.

## Since P vs NP

### Because we don't know if P is NP, we have to settle for comparing hardness.

## Ghosts of Algorithm Students Past

### NP reductions is the hardest part of this course

### Abstract Nonsense!

### Students LIKE solving a problem instance

### Students do NOT LIKE transmogrifying (Calvin and Hobbes) all possible problem instances without solving the problem.

## KEY CONCEPT

### If every example of problem A can be MEANINGFULLY transformed into an example of problem B then problem B is at least as hard as problem A.

## $$ A \leq B$$

## First simple example

### GCD \(\geq\) LCM

#### Someone gives me \(a,b\) and asks for Least Common Multiple.

#### I multiply \(a \cdot b\), divide by \( \gcd(a,b) \), and return the result.

## LCM \(\geq\) GCD

### Since \(a \cdot b = \gcd(a,b) \cdot \textrm{lcm}(a,b)\) we can reverse the trick.

## Another "Easy to Easy" reduction

### Sorting \(\leq\) Convex Hull

## To sort with convex hull do this:

### Map each value in your input, \(x_i\) to the 2-D point \((x_i, x_i^2)\).

### Walk counter clock-wise around your hull.

## So when does this help?

### Suppose problem X has unknown difficulty.

### HARD \(\leq \) X shows that X is tough (if X can be used to solve problem HARD)

### X \(\leq \) EASY shows that X is simple (an EASY problem can solve X)

## When does it NOT help

### X \(\leq\) HARD (a hard problem is at least as hard as X, not useful)

### EASY \(\leq\) X (X can be used to solve an EASY problem)

### If your reduction (the transformation steps) has too high of a complexity.

## Board-Work

### I would like to switch to chalkboard for the rest of the lecture. This is because working through the reductions is best done interactively. For those cramming or following along at home I will list the reductions that I intend to do. I would also recommend watching YouTube videos alongside the book-proofs. I find this stuff much easier to process from a human than from a book (that's just me).

#### SAT to 3SAT

#### 2SAT to Strongly Connected Components

#### 9-15 in the book

#### Hamiltonian Circuit to Traveling Saleman Problem

#### 3-colorability to SAT

#### 2-colorability to SAT (useless)

#### Vertex Cover equivalent to Independent Set equivalent to Clique

#### 3SAT to 3-D Matching

#### 3SAT to Vertex Cover

#### A hint at Vertex Cover to Hamiltonian Circuit

## Neither P nor NP

### Integer Factorization

### Graph Isomorphism

### Discrete Log

## Inteview Question (SO/IRL)

### Given an \( n \times n\) matrix of real numbers. You are allowed to erase any number (from 0 to \(n\)) of the rows and any number (from 0 to \(n\)) of the columns, and after that the sum of the remaining entries is computed. Come up with an algorithm which finds out which rows and columns to erase in order to maximize that sum.