Algorithm Question: We are feeling experimental and want to create a new dish. T

Question

Algorithm Question: We are feeling experimental and want to create a new dish. There are various ingredients we can choose
from and we'd like to use as many of them as possible, but some ingredients don't go well with others.
If there are n possible ingredients (numbered 1 to n), we write down an n x n binary matrix where
the (i, j) entry is 1 if i and j can go together and 0 otherwise. Notice that this matrix is necessarily
symmetric; and that the diagonal entries are always 0.
We wish to solve the following problem:

EXPERIMENTAL CUISINE :
input: n, the number of ingredients to choose from; B, the n x n binary matrix that encodes
which items go well together
output: the maximum number of ingredients which can be selected together
Show that if EXPERIMENTAL CUISINE can be solved in polynomial time, then P=NP.

Explanation / Answer

Given an instance of 3-CNF-SAT with M clauses in N variables, set up 2N ingredients corresponding to true and false for each separate variable and 3M ingredients corresponding to each clause. Set up the discord matrix as follows:

1. All entries are initially zero (go together perfectly).
2. For each variable v, the discord between ingredients "v is true" and "v is false" and vice versa is set to one (perfect discord).
3. For each clause C, calling the corresponding ingredients C1, C2, and C3, set the discords of C1-C2, C1-C3, and C2-C3 (and vice versa) all to one.
4. For each clause, follow this example:

Suppose C is (u or not-v or w). Then set:
discord(C1, u false) = 1
discord(C2, v true) = 1
discord(C3, w false) = 1

A satisying assignment can be converted to a list of ingredients as follows: one of each variable pair is selected as per the assignment (total cost: 0); one of each clause triple that has zero discord with its associated variable is taken: cost 0. [example: for an assignment of false to variable v, we select ingredients "v is false" and we may also select C2]

This gives N + M ingredients with cost zero.

Conversely, suppose you have a set of N + M ingredients with cost 0. It can't have more than two ingredients for the same clause or variable because then the cost is at least one. So the ingredients define an assignment in which each clause is satisfied.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.