## Reduction Redux

#### Andy Novocin

## Daily Challenge

### Prove the following is NP-Complete

### The Longest Path problem

### Input: a Graph and integer \(k\)

### Output: Does G contain a simple path of length \( \geq k\)?

## Longest Path on grid (in P)

## Longest Path on Catan (in NP-Complete)

## Inteview Question (SO/IRL cont.)

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

## Math Challenge

### A Binary \((n, M, d)\)-Code is a set of \(M\) words each is \(n\) characters in \(\{0,1\}\) and the distance between any two is at least \(d\). (Distance is the hamming distance, the number of characters where they differ.)

### Example: \( "00100", "00011", "11111", "11000" \) is a \((5, 4, 3)\)-code.

### Can you develop a \((10, X, 3)\) binary code where X is between 73 and 79?

### An answer nets you a paper.

## Let's look at macho reductions

### What I had intended:

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

### What was accomplished:

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

## Some tips

### Make your source problem as easy as you can

### Make your target problem as hard as you can

### Pick the right source problem

##### (Vertex cover for selection, HC for ordering, Partition for integer, 3SAT for the rest)

### Apply penalties to wrong answers

### Think high level, enforce with gadgets

### If you are stuck try looking for a solution

## Interview Question

### Use a random number generator (rng04) that generates numbers from \(\{0, 1, 2, 3, 4 \}\) with equal probability to write a random number generator that generates numbers from 0 to 7 (rng07) with equal probability. What are the expected number of calls to rng04 per call of rng07?