The game PEBBLES is played on a k × n chessboard. Initially each square of the c
ID: 3577284 • Letter: T
Question
The game PEBBLES is played on a k × n chessboard. Initially each square of the chessboard has a black pebble, or a white pebble, or no pebble. You play the game by removing pebbles one at a time. You win the game if you can end up with a board in which each column contains only pebbles of a single color and each row contains at least one pebble. (a) Show that the set of winnable PEBBLES games is in NP. Hint: Describe a nondeterministic polynomial-time algorithm to determine whether a given PEBBLES board is winnable. (b) Given a boolean expression E in 3-CNF with k clauses and n variables, construct the following k × n board: If literal xi is in clause cj , put a black pebble in column xi , row cj . If literal xi is in clause cj , put a white pebble in column xi , row cj . Show that E is satisfiable if and only if this PEBBLES game is winnable.
Explanation / Answer
a) Show that the set of winnable PEBBLES games is in NP. Hint : Describe a nondeterministic polynomial-time algorithm to determine whether a given PEBBLES board is winnable.
A nondeterministic TM can guess in linear time which set of pebbles should be removed from the initial board. It can then deterministically verify in linear time that the remaining pebbles are arranged so that each column contains pebbles of a single color and each row contains at least one pebble.
b) Given a boolean expression E in 3-CNF with k clauses and n variables, construct the following k × n board: If literal x i is in clause c j , put a black pebble in column x i , row c j . If literal ¬ x i is in clause c j , put a white pebble in column x i , row c j . Show that E is satisfiable if and only if this PEBBLES game is winnable.
If part: Let E be a boolean expression in 3-CNF with k clauses c 1 , c 2 , . . . , c k and n variables x 1 , x 2 , . . . , x n and assume no clause contains both x i and ¬ x i . Suppose the PEBBLES game constructed from E has been won. If all the white pebbles have been removed from column x i leaving only black pebbles, set the corresponding variable x i in E to true. If all the black pebbles have been removed from a column x i leaving only white pebbles, set the corresponding variable x i in E to false. Since every row c j has at least one pebble left in the won game, each clause c j in E has at least one true literal. This means E is satisfiable.
Only if part:SupposeTis a truth assignment that satisfiesE. If xi is set to true,remove all the white pebbles from the corresponding column.Similarly, ifxiis set to false, remove all the black pebbles from the corresponding column. Pebblescorresponding to true literals are left and because every clause has at least one tree literal, every row has at least one pebble.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.