Out: Tuesday, 23-Jan
Due: Tuesday, 30-Jan before class
Decidability of arithmetical theorems
We will consider the state of true theorems in modular arithmetic. Fix a natural number \(q>1\) denote \(\mathbb{Z}_q = \{0,1,\ldots,q-1\}\), and let \(\mathsf{Th}(\mathbb{Z},+,\times)\) be the set of true sentences using quantifiers, logical operators, \(=\) (equality), and the operations \(+\) and \(\times\), where the two operations correspond to addition and multiplication modulo \(q\).
For every \(q>1\), describe how one can think about the set of true sentences as a language over some alphabet, and then argue that your language \(\mathsf{Th}(\mathbb{Z}_q,+,\times)\) is decidable. In other words, there exists a Turing machine that, when given a sentence as input, accepts the sentence if it is true and rejects the sentence if it false.
Further explanation: The quantifiers are \(\forall\) (for all) and \(\exists\) (there exists), and the logical operators are \(\wedge\) (and), \(\vee\) (or), \(\neg\) (negation), and \(\rightarrow\) (implication). For instance, here is the statement that every number has an additive inverse modulo \(q\):
\[\forall x \exists y (x+y=0)\]
This sentence is true. Here is the statement that every number has a multiplicative inverse modulo \(q\):
\[\forall x \exists y (xy=1)\]
This statement is never true (because \(0\) does not have an inverse). On the other hand, the following statement is a true theorem if and only if \(q\) is prime:
\[\forall x (\neg (x=0) \rightarrow \exists y\ xy=1)\]
Here, \(q\) is fixed (it is not part of the input), and your Turing machine should decide whether or not the formula is true.
[It is a fascinating fact--sketched in class--that if we work instead over the integers, the corresponding theory is undecidable. This is because there exists a computable reduction that maps an input \(\langle M,w\rangle\) to a sentence \(\phi_{M,w}\) in \(\mathsf{Th}(\mathbb{Z},+,\times)\) such that \(M\) accepts \(w\) if and only if \(\phi_{M,w}\) is true. Basically, arithmetic contains a universal Turing machine!]
Computing a long path when \(\mathsf{P}=\mathsf{NP}\)
Show that if \(\mathrm{LONGPATH} \in \mathsf{P}\), then the following can be computed in polynomial time: Given a graph \(G\) and two vertices \(a,b\) in \(G\) as input, output the longest simple path from \(a\) to \(b\) in \(G\).
Note that \(\mathsf{P}\) contains decision problems, but you are asked to here to output the longest path (say, the sequence of vertices in some longest path).
[Hint: First consider how to compute the length of the longest path by deciding multiple instances of the \(\mathrm{LONGPATH}\) problem. Now solve even more instances---but only polynomially many!---to eventually compute an entire longest path.]
Show that every language in \(\mathsf{TIME}(n)\) can be recognized by a DFA.
Suppose we have \(n\) variables \(x_1,x_2,\ldots,x_n\) and each variable can take only value \(0\) or \(1\). We also have an expression of the form: \[C_1 \cdot C_2 \cdot C_3 \cdots C_m\] where each \(C_i\) is of the form \(C_i=\max(a_i,b_i)\) and each \(a_i\) or \(b_i\) is a variable \(x\) or \(1-x\).
For instance, consider the following expression over the variables \(x_1,x_2,x_3\): \[ E = \max(x_1,1-x_2) \cdot \max(1-x_1,x_3)\cdot \max(x_1,x_3) \cdot \max(x_2,1-x_3). \] You are given such a formula as input and the goal is to decide if there exists a setting of the variables to \(0/1\) v alues such that the expression equals \(1\). For example, for \(E\) there is a solution: \[ x_1 = 1, x_2 = 1, x_3 = 1\,.\] Plugging these in we get \(E = \max(1,0)\cdot \max(0,1)\cdot\max(1,0) = 1\cdot 1 \cdot 1 = 1.\)
On the other hand, the expression \[ \max(x_1,1-x_2)\cdot \max(1-x_1,1-x_2)\cdot \max(x_1,x_2)\cdot \max(1-x_1,x) = 1 \] has no solution.
Consider the language of formulas of this form that have a solution. Show that this language is in \(\mathsf{P}\) (polynomial time).