Chapter 0: Introduction

We generally believe that PATH is not NP-complete. Explain the reason behind this belief. Show that proving PATH is not NP-complete would prove P ≠ NP

Prove that an oracle C exists for which${\mathrm{NP}}^{\mathrm{c}}\ne {\mathrm{coNP}}^{\mathrm{c}}$ .

Prove that there exists an undecidable subset of ${\left\{1\right\}}^{*}$.

Let $P=\left\{a,b\right\}.$Give a CFG generating the language of strings with twice as many$a\text{'}sasb\text{'}s$ . Prove that your grammar is correct.

Let $AMBI{G}_{CFG}=\left\{<G>|GisanambiguousCFG\right\}$. Show that AMBIG_CFG is undecidable. (Hint: Use a reduction from PCP. Given an instance

$P=\left\{\left[\frac{t_1}{b_1}\right],\left[\frac{t_2}{b_2}\right],\dots ,\left[\frac{t_k}{b_k}\right]\right\}$

of the Post Correspondence Problem, construct a CFG Gwith the rules

$S\to T|B$

$T\to t_1{T}_{a_1}|.....|t_k{T}_{a_k}\left|t_1{a}_1\right|....|t_k{a}_k$

$B\to b_{1}B|...|b_1{B}_{a_k}|...|b_k{a}_k$

where a₁,...,a_k are new terminal symbols. Prove that this reduction works.)

A k-query oracle Turing machine is an oracle permitted to make at most k queries on each input. A k-query oracle Turing machine ‘M’ with an oracle for A is written${\mathrm{M}}^{\mathrm{A},\mathrm{k}}$ . Define ${\mathrm{P}}^{\mathrm{A},\mathrm{k}}$to be the collection of languages that are decidable by polynomial time k-query oracle Turing machines with an oracle for ‘A’.

1. Show that$\mathrm{NP}\cup \mathrm{coNP}\subseteq {\mathrm{P}}^{\mathrm{SAT},1}$
2. Assume that . Show that$\mathrm{NP}\cup \mathrm{coNP}\not\subset P^{\mathrm{SAT},1}$ .

Show how to compute the descriptive complexity of strings K(x) with an oracle for A_TM.

In certain programming languages, comments appear between delimiters such as #and $\#/$. Let Cbe the language of all valid delimited comment strings. A member of Cmust begin with $\#/$and end with $\#/$but have no intervening $\#/$. For simplicity, assume that the alphabet for Cis $\sum =\{a,b,/,\#\}$.

a. Give aDFA that recognizes C.

Let $\mathit{C}\mathbf{=}\mathbf{\{}\mathit{x}\mathbf{\#}\mathit{y}\mathbf{|}\mathit{x}\mathbf{,}\mathit{y}\mathbf{\in }\left\{0,1\right\}\mathbf{*}\mathit{a}\mathit{n}\mathit{d}\mathit{x}\mathbf{\ne }\mathit{y}\mathbf{\}}\mathbf{.}$Show that$\mathit{C}$ is a context-free language.