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 arepossible ingredients (numbered $1$to $n$), we write down an matrix giving thediscordbetween any pair of ingredients. Thisdiscordis a real number between $0.0$and $1.0$, where means “they go together perfectly” and $1.0$ means “they really don’t go together.” Here’s an example matrix when there are five possible ingredients.

In this case, ingredients $2$and $3$go together pretty well whereas$1$and$5$clash badly. Notice that this matrix is necessarily symmetric; and that the diagonal entries are always . $0.0$Any set of ingredients incurs apenaltywhich isthe sum of all discord values between pairs of ingredients.For instance, the set of ingredients$\{1,3,5\}$incurs a penalty of $0.2+1.0+0.5=1.7$

.We want this penalty to be small.

EXPERIMENTAL CUISINE

Input:, $n$the number of ingredients to choose from $D$;,the $n\times n$“ discord” matrix; some number$p\ge 0$

OUTPUT:The maximum number of ingredients we can choose with penalty $\le p$.

Show that ifEXPERIMENTAL CUISINEis solvable in polynomial time, then so is 3SAT.

Step by step solution

01

Statement

Remember the data:

For some high-quality regular languages, aset of rules have polynomial-timeif its strolling time is higher constrained by means of a polynomial expression within the length of the technique’s input.

The Boolean satisfiability problem, additionally known as the propositional satisfiability hassle that is abbreviated as SATISFIABILITY, SAT, or B-SAT. It is the task of finding if there may be a proof that fulfills a provided Boolean formula.

02

Step 2:Show that if EXPERIMENTAL CUISINE is solvable in polynomial time, then so is 3SAT

Consider that the EXPERIMENTAL CUISINE is a generalization of INDEPENDENT SET.

To identify an independent set whose sizeisin a graph $G=(V,E)$,construct the following example of the EXPERIMENTAL CUISINE problem with $n=\left|V\right|$ingredients.

Consider penalty $p=0$and let the discord between ingredient $i$and$j$be $1$ if $(i,j)\in E$and assume that it is zero otherwise.

ingredients can be selected with a total penalty$p=0$ if there is an independent set of size $s$.

Hence, if EXPERIMENTAL CUISINE can be solved in polynomial time, then INDEPENDENT SET can also be solved in polynomial time. It is already known that INDEPENDENT SET is NP-complete.

Therefore, if INDEPENDENT SET can be solved in polynomial time, then every problem in NP can be solved in polynomial time including 3SAT.

Unlock Step-by-Step Solutions & Ace Your Exams!

• Full Textbook Solutions

  Get detailed explanations and key concepts

• Unlimited Al creation

  Al flashcards, explanations, exams and more...

• Ads-free access

  To over 500 millions flashcards

• Money-back guarantee

  We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!