Learning Materials
Features
Discover
Chapter 7: Q14P (page 323)
A permutation on the set is a one-to-one, onto function on this set. When is a permutation, means the composition of with itself t times. Let
Show that . (Note that the most obvious algorithm doesn鈥檛 run within polynomial time.
Therefore, the solution is,
Over 30 million students worldwide already upgrade their learning with 91影视!
All the tools & learning materials you need for study success - in one app.
Get started for free
Show that if P=NP , a polynomial time algorithm exists that takes an undirected graph as input and finds a largest clique contained in that graph. (See the note in Problem 7.38.)
A triangle in an undirected graph is a . Show that , where
This problem investigates resolution, a method for proving the unsatisfiability of cnf-formulas. Let be a formula in cnf, where the are its clauses. Let . In a resolution step, we take two clauses and in C, which both have some variable occurring positively in one of the clauses and negatively in the other. Thus, and , where the and are literals. We form the new clause and remove repeated literals. Add this new clause to C. Repeat the resolution steps until no additional clauses can be obtained. If the empty clause ( ) is in C, then declare unsatisfiable. Say that resolution is sound if it never declares satisfiable formulas to be unsatisfiable. Say that resolution is complete if all unsatisfiable formulas are declared to be unsatisfiable.
a. Show that resolution is sound and complete.
b. Use part (a) to show that .
A cut in an undirected graph is a separation of the vertices V into two disjoint subsets S and T . The size of a cut is the number of edges that have one endpoint in S and the other in T . Let
Show that MAX-CUT is NP-complete. You may assume the result of Problem 7.26. (Hint: Show that. The variable gadget for variable x is a collection of 3c nodes labeled with x and another nodes labeled with x . The clause gadget is a triangle of three edges connecting three nodes labeled with the literals appearing in the clause. Do not use the same node in more than one clause gadget. Prove that this reduction works.)
What do you think about this solution?
We value your feedback to improve our textbook solutions.
Explanations 
Textbooks 
Flashcards 
91影视 AI 
Notes 
Study Plans 
Study Sets 
Find a degree 
Magazine