CS/ECE 374 A (Spring 2022) Homework 11

发布时间：2022-04-28

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS/ECE 374 A (Spring 2022)

Homework 11

Problem 11.1: Consider the following problem CoLoRFuL-WALK (which is an extension of Prob- lem 8.2(b) from HW8):

Input: a directed graph G = (V, E) with n vertices and m edges, a vertex s e V , and a color c(e) e {1, . . . , k} for each edge e e E, and a number l.

Output: “yes” iﬀ there exists a walk that starts at s and encounters at least l distinct colors.

Consider the SET-CovER problem:

Input: a set X of N elements, a collection of M subsets s = {S1, . . . , SM } where each Si S X, and a number K .

Output : “yes” iﬀ there exists a subcollection T S s of K subsets, such that the union of the subsets in T includes all elements of X .

Describe a polynomial-time reduction from SET-CovER to CoLoRFuL-WALK. Follow these steps:

❼ Given an input to SET-CovER (i.e., X , s, and K), describe a construction of an input to

CoLoRFuL-WALK (i.e., G, s, c(.), and l). Check that your construction takes polynomial time.

❼ Prove that the input to SET-CovER has a “yes” answer if and only if your input to

CoLoRFuL-WALK has a “yes” answer.

Since SET-CovER is a well-known NP-hard problem, it would then follow that CoLoRFuL- WALK is NP-hard.

(Hint: for your construction of the directed graph G, try something like the picture below, with appropriate colors assigned to edges. Remember that in the actual description of your construction, you are given X , s, and K; you are not given T, which may or may not exist, since the goal is to determine whether the answer is “yes” or “no”.)

Problem 11.2: By now, everyone has heard of Wordle, the online word-guessing game. Here, you will consider a tougher variant of the game, where the word length n is a variable, all strings of length n from a ﬁxed alphabet are legal words (no dictionary needed!), and after each guess, you are only told whether there is a green (matching) position, but not the number of green (nor yellow) positions, nor where they are exactly. You will show that in this version of the game, just deciding whether there exists a solution after a series of guesses is already hard (so forget about the question of how to generate a good next guess!).

If you didn’t follow the above paragraph, don’t worry—here is the precise deﬁnition of our problem: For two strings y and z of length n, ﬁrst deﬁne match(y, z) to be true if there exists a position k such that the k-th symbol of y is equal to the k-th symbol of z, and false otherwise. The statement of the ToucH-WoRDLE problem is as follows:

Input: a ﬁnite alphabet Σ, a list of m strings y1 , . . . , ym e Σn , and m Boolean values b1 , . . . , bm e {true, false}.

Output: “yes” iﬀ there exists a string z e Σn such that match(yi, z) = bi for each i = 1, . . . , m.

(Example: on the input with Σ = {A, B, C}, y1 = AAAA, b1 = true, y2 = BBCC , b2 = true, y3 = BCAB , b3 = false, the answer is “yes”, e.g., by choosing z = ABCC.)

Describe a polynomial-time reduction from 3SAT to ToucH-WoRDLE. Follow these steps:

❼ Given an input to 3SAT (i.e., a Boolean formula F in 3CNF form), describe a con-

struction of an input to ToucH-WoRDLE (i.e., an alphabet Σ, and a list of strings and Boolean values). Check that your construction takes polynomial time.

❼ Prove that F is satisﬁable if and only if your input to ToucH-WoRDLE has a “yes”

answer.

Since 3SAT is NP-hard, it would then follow that ToucH-WoRDLE is NP-hard.

(Hint: in your construction, an alphabet of size 3 (0, 1, and an extra symbol) would be suﬃcient. Suppose F has n variables and m clauses. Intuitively, the string z (if exists) should correspond to a satisfying assignment of F (if exists). For each clause Ci, construct a string yi of length n (and a corresponding Boolean value bi) to somehow make sure that z contains at least one true literal of Ci. Also, construct an extra string to somehow make sure that z uses only 0s and 1s and not the extra symbol. . . Remember that in the actual description of your construction, all you are given is F ; you are not given a satisfying assignment, which may or may not exist, since the goal is to determine whether the answer is “yes” or “no”.)