Homework #1

CSE 531, Spring 2018

Due: 13-Apr

Problem 1

Consider a language $A \subseteq \Sigma^*$ consisting of a subset of Turing machine descriptions. Say that $A$ is semantic if $\langle M\rangle \in A$ and $\mathcal{L}(M)=\mathcal{L}(N) \implies \langle N\rangle \in A$, where we recall that $\mathcal{L}(M) = \{ x \in \Sigma^* : M \textrm{ accepts } x \}$.

Prove that there are only two languages that are both semantic and decidable.

Problem 2

Consider some alphabet $\Sigma \subseteq \{0,1,2,3\}$. Say that a language $L \subseteq \Sigma^*$ is ISOD-enumerable (for “increasing sum of digits enumerable”) if it can be enumerated by a Turing machine in an order $x_1, x_2, x_3, \ldots$ such that each string in $L$ appears exactly once, and the sum of the digits in $x_{i+1}$ is always at least the sum of the digits in $x_i$ for each $i=1,2,3,\ldots$.

Such an enumerator could output the sequence $112, 123, 11212, 322, \ldots$, but $123$ cannot be followed by $112$.

Give a characterization of which alphabets $\Sigma \subseteq \{0,1,2,3\}$ are such that

$L \subseteq \Sigma^*$ is decidable $\iff$ $L$ is ISOD-enumerable,

and prove that your characterization is correct.

Problem 3

Review the definition of a context-free grammar (CFG). If $G$ is a CFG, we let $\mathcal{L}(G)$ denote the language that $G$ generates. In the following, $(01)^* = \{ \epsilon, 01, 0101, 010101, 01010101, \ldots\}$, where $\epsilon$ is the empty string.

As Farzam pointed out, only one of the following statements can be true. Decide which is true and prove it:

Problem 4

  1. A vertex cover in an undirected graph $G=(V,E)$ is a subset of nodes $C \subseteq V$ such that every edge has at least one endpoint in $C$. A dominating set of $G$ is a set of nodes $D \subseteq V$ such that every node in $G$ is in $D$ or has a neighbor in $D$. Define the languages:

    \begin{align*} \textrm{VERTEX-COVER} &= \left\{ \langle G,k \rangle : G \textrm{ has a vertex cover of size at most } k \right\} \\ \textrm{DOM-SET} &= \left\{ \langle G,k\rangle : G \textrm{ has a dominating set of size at most } k \right\}. \end{align*}

    Prove that $\textrm{VERTEX-COVER} \leq_P \textrm{DOM-SET}$.
  2. An undirected graph is $3$-colorable if there is an assignment of the colors {red, blue, green} to the vertices such that no pair of vertices connected by an edge have the same color. Show that if P=NP, then there is a polynomial-time algorithm to find a $3$-coloring of a graph. (Recall that NP is a class of languages, i.e., problems with yes/no answers, thus the fact that $3$-coloring is in NP does not solve the problem without saying more.)

Problem 5

Consider a mapping $\varphi : \Sigma \to \Sigma^+$ that maps characters of the alphabet to finite length strings (recall that $\Sigma^+$ is the set of finite length strings over $\Sigma$ whose length is at least 1). For a word $w = w_1 w_2 \cdots w_n \in \Sigma^*$, we define

$$ \varphi(w) = \varphi(w_1) \varphi(w_2) \cdots \varphi(w_n). $$ Consider the following two statements:

  1. $\mathsf{P}=\mathsf{NP}$
  2. For every language $L \in \mathsf{P}$ and $\varphi$ as above, the language $\{\varphi(w) : w \in L\}$ is also in $\mathsf{P}$.