DIT602/TIN093-Assignment 6 Chemical Compound Safety and P, NP and NP-complete Solved

1         Chemical Compound Safety
A company operating in the chemical industry produces a set R of n different compounds, and currently have two production plants, A and B. They have gathered m different studies to identify potentially dangerous combinations of two or more chemical compounds from their range of products: for each of the combinations, the company wants to take precaution and not produce all of them at the same plant. The question then becomes whether it is possible for the company to produce the n compounds following this safety measure.

More formally, given:

•    the set R = {r1,...,rn} of n compounds to be produced

•    the collection of m unsafe combinations of compounds K = {K1,...,Km}, where for each i,Ki ⊆ R and |Ki| ≥ 2

Is it possible to split the company’s production between the two plants and still produce all compounds {r1,...,rn}? That is, are there groupings of compounds

RA,RB ⊆ R such that RA ∪ RB = R, RA ∩ RB = ∅, and for each i = 1,...,m both Ki 6⊆ RA and Ki 6⊆ RB. Let’s denote this problem as CCompat.

Your task is to show that this decision problem is NP-complete. To do so:

1.   Show that CCompat is in NP.

2.   Give a polynomial-time reduction from the following modified 3-SAT problem, which we shall call 3-SAT-bis, to the company’s problem:

Given disjunctive clauses C1,...,Ct over a set of Boolean variables X = {x1,...,xq}, being each clause Ci of length 3. Is there a satisfying truth assignment over X such that for each i the assigned truth values to the disjuncts of Ci are not all the same?

This modification of 3-SAT is known to be NP-complete, a fact which you may use for this problem.

turn page for a guide and some hints

1

A guide to providing the polynomial-time reduction:

1.   Provide a translation from 3-SAT-bis to CCompat: create an instance ofCCompat given the input to 3-SAT-bis (clauses C1,...,Ct over variables {x1,...,xq}). Show this translation is polynomial in time.

 Hint: For the translation, think about what the constraints on the possible, different disjuncts should look like. Don’t forget that both xj and xj may appear as disjuncts, and that for each Ci not all disjuncts should be assigned the same value - i.e.: there should be at least one disjunct assigned 0 and one assigned 1 per clause.

2.   Show that if the translated instance of CCompat has a split into two setsRA,RB (constrained as above), then there is a satisfying assignment for the clauses in 3-SAT-bis.

3.   Show that if there is a satisfying assignment in 3-SAT-bis, then the translated instance of CCompat has a pair of sets RA,RB (constrained as above).

After providing the reduction, briefly explain why it entails the NP-completeness of CCompat.

Note: As a reminder (p.459 in the course book), for our set of variables X:

•    each Boolean variable xj can take a value of either 0 or 1 (correspondingly, false or true as truth values)

•     a disjunctive clause of length 3 has the form t1∨t2∨t3, where each disjunct tk is either a variable xj or its negation xj

•    a truth assignment for X is a function ν : X → {0,1}

•    an assignment satisfies a clause Ci if it causes it to evaluate to 1 under the rules of Boolean logic.

A satisfying assignment with respect to C1,...,Ct is one which satisfies all clauses, i.e.: it satisfies the conjunction C1 ∧ C2 ∧ ... ∧ Ct.

2         P, NP and NP-complete
Given three decision problems X,Y and Z. Given further that X ∈ P, Y ∈ NP and Z ∈ NP-complete. Also assume that you managed to establish that Y ≤p X and Y ≤p Z. What conclusions can you draw and why?