Consider a special version of 3-SAT that requires that each variable has exactly 3 occurrences, but...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Consider a special version of 3-SAT that requires that each variable has exactly 3 occurrences, but allows each clause to have either 2 or 3 literals. Let's call this problem 2,3-SAT3. Here is an example of an instance of 2,3-SAT3 problem: (x1 V2 V3) A (1V 2V 4) A (x1 V4) A (2 VT3) A (x3 V14) Note that each variable has exactly 3 occurrences. We want to show that 2,3-SAT3 is NP-hard. Follow the following steps to reduce 3-SAT to 2,3-SAT3 For simplicity, you may assume that in each instance of 3-SAT, every variable has at least 2 occurrences. (a) Given variables y1, y2,..., Yk, k > 2, design a set of 2-literal clauses such that there are exactly two assignments for these variables that satisfy the set of your designed clauses: (i) y = y2 = ... = Yk = false, and (ii) y = Y2 = ... = Yk = true. Each variable should have exactly 2 occurrences in these clauses. (b) Now consider an instance S of 3-SAT in which variable x; has k 2 occurrences. Using part (a) construct a new instance S' by replacing all occurrences of x; with new variables y1,..., yk. Add necessary clauses to make the original instance S and the new instance S' equivalent (one is satisfiable if and only if the other is satisfiable). Argue why each of these new variables has exactly 3 occurrences in S'. (c) Describe a reduction from 3-SAT to 2,3-SAT3 as an algorithm. (d) Prove correctness of your reduction! Bonus. Describe a reduction from 3-SAT to 2,3-SAT3 without assuming the simplifying assumption (that each variable in 3-SAT instance has at least 2 occurrences). Activ Consider a special version of 3-SAT that requires that each variable has exactly 3 occurrences, but allows each clause to have either 2 or 3 literals. Let's call this problem 2,3-SAT3. Here is an example of an instance of 2,3-SAT3 problem: (x1 V2 V3) A (1V 2V 4) A (x1 V4) A (2 VT3) A (x3 V14) Note that each variable has exactly 3 occurrences. We want to show that 2,3-SAT3 is NP-hard. Follow the following steps to reduce 3-SAT to 2,3-SAT3 For simplicity, you may assume that in each instance of 3-SAT, every variable has at least 2 occurrences. (a) Given variables y1, y2,..., Yk, k > 2, design a set of 2-literal clauses such that there are exactly two assignments for these variables that satisfy the set of your designed clauses: (i) y = y2 = ... = Yk = false, and (ii) y = Y2 = ... = Yk = true. Each variable should have exactly 2 occurrences in these clauses. (b) Now consider an instance S of 3-SAT in which variable x; has k 2 occurrences. Using part (a) construct a new instance S' by replacing all occurrences of x; with new variables y1,..., yk. Add necessary clauses to make the original instance S and the new instance S' equivalent (one is satisfiable if and only if the other is satisfiable). Argue why each of these new variables has exactly 3 occurrences in S'. (c) Describe a reduction from 3-SAT to 2,3-SAT3 as an algorithm. (d) Prove correctness of your reduction! Bonus. Describe a reduction from 3-SAT to 2,3-SAT3 without assuming the simplifying assumption (that each variable in 3-SAT instance has at least 2 occurrences). Activ
Expert Answer:
Related Book For
Applied Regression Analysis and Other Multivariable Methods
ISBN: 978-1285051086
5th edition
Authors: David G. Kleinbaum, Lawrence L. Kupper, Azhar Nizam, Eli S. Rosenberg
Posted Date:
Students also viewed these programming questions
-
"internet radios" for streaming audio, and personal video recorders and players. Describe design and evaluation processes that could be used by a start-up company to improve the usability of such...
-
can someone solve this Modern workstations typically have memory systems that incorporate two or three levels of caching. Explain why they are designed like this. [4 marks] In order to investigate...
-
The Quality Athletics Company produces a wide variety of sports equipment. Its newest division, Golf Technology, manufactures and sells a single product AccuDriver, a golf club that uses global...
-
Find the perimeter of the triangle with vertices A(8, - 2), B(1, 5), and C(4, - 5).
-
Bianca Bicycle Company manufactures mountain bikes with a variable cost of $200. The bicycles sell for $350 each. Budgeted fixed manufacturing overhead for the most recent year was $2,200,000....
-
A bicyclist pedals a distance \(d\) at constant speed on a level stretch of road. She then pedals up a hill and passes slowly over the top. As she coasts down the other side of the hill, she applies...
-
Iverson Company had the following assets and liabilities on the dates indicated. Iverson began business on January 1, 2013, with an investment of $100,000. Instructions From an analysis of the change...
-
What did you think about the two contrasting patterns in this chapter? Do you or someone you know fit one or the other of these patterns? Which pattern do you think is more likely to emphasize...
-
The following information is known about a company: its operating assets the current year, 2019, are $700 million and are expected to grow at a rate of 12% per year through 2022. Its operating...
-
Open the structure file for problem 3.40: this shows the structure of C 2 Cl 6 in the preferred staggered conformation. (a) Orientate the structure so you are looking along the CC bond. You should be...
-
Which diagrams represent the time-based nature of a system?
-
Identify the constructs expressing the links, associations and relationships among objects in a system.
-
(a) Explain what is meant by corporate social responsibility. (150 words) (b) Explain why reporting of corporate social responsibility is seen as important to a study of accounting. (150 words)
-
Which diagrams will you use if you need to show the physical relationship between software components and the hardware in the delivered system?
-
Answer the following questions as you watch the video Biography of Hokusai (BBC Documentary) (44 minutes)= 1) What do you know about the artist Katsushika Hokusai? (Some important information is also...
-
Marc Company assembles products from a group of interconnecting parts. The company produces some of the parts and buys some from outside vendors. The vendor for Part X has just increased its price by...
-
In the STAR experiment (Section 7.5.3), children were randomly assigned within schools into three types of classes: small classes with 13-17 students, regular-sized classes with 22-25 students, and...
-
Professor Ray C. Fair's voting model was introduced in Exercise 2.23. He builds models that explain and predict the U.S. presidential elections. See his website at...
-
Many cities in California have passed Inclusionary Zoning policies (also known as below-market housing mandates) as an attempt to make housing more affordable. These policies require developers to...
Study smarter with the SolutionInn App