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?