CS 3800
Fall 2024
Homework 11
1. [10 Points] Language problems. Let
E = {⟨M⟩ | M is a DFA that accepts some string with more 1’s than 0’s}
Show that E is decidable. (Hint: Theorems about CFLs are helpful here).
2. [14 Points] Explicit mapping reduction. Let Σ = {0, 1}
(a) Consider the following languages A, B ⊆ Σ
∗
:
A = {w ∈ Σ* | w has the substring 1110111}
B = {w ∈ Σ* | w does not have the substring 1110111}
Show that A ≤m B by defining an explicit reduction f from A to B.
(b) Is it always the case that A ≤m A for languages A ⊆ Σ
∗
? Prove your statement (use results from lecture for a simplest proof).
3. [6 Points] Reductions from decidable languages. Let A, B ⊆ Σ
∗ and assume that A is decidable. For each of the following statements give either a proof or a counterexample.
For full credit, use results from class, when available.
(a) A ≤T B
(b) A ≤m B
4. [13 Points] Mapping reductions.
(a) Show that for each Turing machine M there exists a Turing machine Mc such that
– M never prints a blank
– L(M) = L(M)
(b) Consider the problem of determining whether, started on a blank tape, a Turing machine will ever print a blank. Formulate this problem as a language and show that it is undecidable: use a mapping reduction from Accept-Empty (lecture 22b).
5. [15 Points] Mapping reductions. An unreachable state in a Turing machine is one that is never entered on any input string. Consider the problem of determining whether a Turing machine has any unreachable states. Formulate this problem as a language and use a reduction from Accept-Empty to show that it is undecidable.
6. [10 Points] Mapping reductions to ATM. Let Σ = {0, 1}. Which, if any, of the following languages are mapping-reducible to ATM ? Give simplest proofs using results from lecture or homework
(a) L1 = {< M >| M is a TM that accepts at least one string consisting only of 1’s}
(b) L2 = {< M >| M is a TM that accepts no input}
7. [12 Points] Languages in NP that aren’t NP-complete Give two languages that are in NP but are not NP-complete. Explain why these languages aren’t NP-complete.
8. [20 Points] Sudoku. The game of Sudoku takes as input a n2 × n2 grid partitioned in blocks of size n × n. Each cell of the grid is to be filled with an integer from 1 to n2 so that each row, each column, and each block contains all of the integers from 1 to n2. Some of the cells have been pre-filled, so that the question is whether or not the other cells can be filled so as to satisfy all conditions.
(a) Does the following Sudoku problem have a solution? If yes, show that solution, if no explain why there is no solution.
(b) Explain why Sudoku ∈ NP (the input is a partially filled n
2 × n
2 array). Your explanation may be based on the informal definition of NP, on its expression with an existential quantifier, or on nondeterministic machines.
Given that SAT is NP-complete and Sudoku ∈ NP, we have Sudoku ≤p SAT. The next few questions construct an explicit reduction from Sudoku to SAT. For simplicity we do this in the case of 4 × 4 grids.
That is, for each partially filled 4 × 4 grid S, we construct a CNF ΦS such that S has a solution iff ΦS is satisfiable.
ΦS uses variables xi,j,k (1 ≤ i, j, k ≤ 4) that are true iff the cell in row i and column j contains value k. ΦS will be the conjunction of several clauses, each representing a condition that must be satisfied.
(c) Write a CNF Φpre that is true if and only if the prefilled cells have the content indicated in the figure of part (a).
(d) Next, we must ascertain that each cell contains a number. Write a clause Φij that is true iff the cell in row i and column j contains a number.
(e) We should also write a CNF Φrow i guaranteeing that no two cells in row i (1 ≤ i ≤ 4) contain the same number. Φrow i
is obtained as conjunction
Φrow i = Φrow i, 1 ∧ Φrow i, 2 ∧ Φrow i, 3 ∧ Φrow i, 4
where Φrow i, k is a CNF expressing that no two different cells in row i have value k. Write the CNF Φrow i, k.
(f) Similarly, write a CNF Φcol j, k expressing that no two different cells in column j have value k.
(g) Lastly, no two cells in the same block should contain the same number. Write a CNF Φblock 1,1,k ensuring that no two different cells in the top-left block (containing cell (1, 1)) have value k.
(h) Do we need to add a CNF preventing a cell from containing two different numbers?
(i) We obtain ΦS as conjunction of expressions of the above types. What is the total number of clauses in ΦS? Explain your count by giving the number of clauses of each type (c) through (g).