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\)?

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.

Practice Tests Available

Let's look at macho reductions

Karp's 21 NP Complete Problems

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?