Best代写-最专业靠谱代写IT | CS | 留学生作业 | 编程代写Java | Python |C/C++ | PHP | Matlab | Assignment Project Homework代写

算法代写|CS/ECE 374 A

算法代写|CS/ECE 374 A



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 fixed 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 definition of our problem: For two strings y and z of length n, first define 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 TOUGH- WORDLE problem is as follows:

Input: a finite alphabet 2, a list of m strings ….,Ym∈E”, and m Boolean values …..m∈{true, false}.

Output:“yes” iff there exists a string z∈En such that match(yi;,z)= b; for each i= 1…,.m.

(Example: on the input with 8={A,B,C},y= AAAA,b1 = true, yn = 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 TOUGH-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 TOUGH- WORDLE (ie., an alphabet E, and a list of strings and Boolean values). Check that your construction takes polynomial time.
  • Prove that F is satisfiable if and only if your input to TOUGH-WORDLE has a“yes”answer.

Since 3SAT is NP- hard, it would then follow that TOUGH- WORDLE is NP-hard.

(Hint: in your construction, an alphabet of size 3 (0, 1, and an extra symbol) would be suficient. 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 symbo… 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”.)