Problem 1: Does the instance of PCP with pairs (01,12), (0,01), (12,20), and (2,0) have a solution? Either find one or give a proof that it does not.

Problem 2: The Chain-Selection Problem is: given

1. A budget m,
2. A target t,
3. A directed graph G that consists of disjoint chains only (a chain is a sequence of nodes n₁, n₂,..., n_k, such that the only arcs among these nodes are from n_i to n_i+1, for i = 1, 2,..., k-1), and
4. A value v_i for each node n_i,

can we select m nodes, whose values sum to at least t, subject to the constraint that if we select a node, then we must select its predecessor, if any, in its chain?

Example: An example of a chain graph has nodes 1, 2,..., 10 and arcs 1→2, 2→3, 3→4, 6→7, 7→8, 8→9, and 9→10. The chains are 1-2-3-4, 5, and 6-7-8-9-10. In this graph, with a budget of 4, we could choose nodes {1, 2, 5, 6}, or {6, 7, 8, 9}, for example, but we could not choose {1, 2, 7, 8}, because it is not permitted to choose 7 without choosing its predecessor 6 in its chain.

Your question: Is the Chain-Selection Problem NP-complete or is it in P? Either give a reduction to show it is NP-complete or give a polytime algorithm to solve it.

Aside: This problem actually surfaced recently as a problem about materialized-view selection in databases. However, we can see it as one of choosing items to purchase in an environment where it doesn't make sense to purchase one item until you have purchased all the previous items on a chain. For instance, one chain might be "a TV" → "cable service" → "high-def decoder box." It doesn't make sense to buy cable service if you have no TV, and it doesn't make sense to get a decoder box unless you have cable service.

A Hint is available.

Problem 3: The Quadratic Allocation Problem is: given

1. Nonnegative integers a and b,
2. A list of integers i₁, i₂,..., i_k, and
3. An integer limit l,

can we select a subset of the integers on the list i₁, i₂,..., i_k, such that the sum of ai+bi² over all selected integers i equals the limit l? Note: all integers are assumed represented in binary for this problem.

Is the Quadratic Allocation Problem NP-complete or is it in P? Either give a reduction to show it is NP-complete or give a polytime algorithm to solve it.

Aside: This problem arose during some consulting I was doing, where the integers represented the sizes of different software jobs, and the quadratic term is there because the cost of implementing software goes up faster than linearly with the size of the job.

A Hint is available.