Chapter 0: Introduction

Show that A is Turing-recognizable $A_m\le A_{TM}$

Use the result of Problem 6.21 to give a function f that is computable with an oracle for A_TM, where for each n,f(n) is an incompressible string of length n.

Show that A is decidable iff $A{\le }_m{0}^{*}1*$.

Show that the function K(x) is not a computable function.

Let it$B$ be any language over the alphabet $\sum$. Prove that $B=B+iffBB\subseteq B$

Let $\mathbf{HALF}-\mathbf{CLIQUE}=\{<\mathbf{G}>|\mathbf{G}$s an undirected graph having a complete subgraph with at least$\mathbf{m}/\mathbf{2}$ nodes, where m is the number of nodes in$\mathbf{}\mathit{G}$. Show that HALF-CLIQUE is NP-complete.

Recall that you may consider circuits that output strings over $\{0,1\}$, by designating several output gates.

Let's${\mathrm{add}}_{\mathrm{n}}:\{0,1{\}}^{2\mathrm{n}}\to {\{0,1\}}^{\mathrm{n}+1}$take two n bit binary integers and produce the n+1 bit sum. Show

that you can compute the${\mathrm{add}}_{\mathrm{n}}$function with$\mathrm{O}\left(\mathrm{n}\right)$size circuits.

Let $J=\left\{w\right|$either$w=0x$for some,$x\in A_{TM}$ or$w=1y$for some $y\in \overline{A_{TM}}\}$. Show that neither Jnor$\overline{J}$is Turing-recognizable.

Let $\mathbf{CNFk}=\left\{\right\}$ is a satisfiable cnf-formula where each variable appears in at most k places}.

a. Show that$\mathbf{CNF}\mathbf{2}?\mathbf{P}$ .

b. Show that$\mathbf{CNF}\mathbf{3} \mathbf{is}\mathbf{NP}$-complete.

Define the function ${\mathrm{majority}}_{\mathrm{n}}:\{0,1{\}}^{\mathrm{n}}\to \{0,1\}$as

$$\begin{gathered} {\mathrm{majority}}_{\mathrm{n}}({\mathrm{x}}_1,\dots ,{\mathrm{x}}_{\mathrm{n}})=\left\{0\sum {\mathrm{x}}_{\mathrm{i}}<\frac{\mathrm{n}}{2}; \\ 1\sum {\mathrm{x}}_{\mathrm{i}}⩾\frac{\mathrm{n}}{2}. \\ \right. \end{gathered}$$

Thus, the${\mathrm{majority}}_{\mathrm{n}}$function returns the majority vote of the inputs. Show that itcan be computed with:

1. $\mathrm{O}({\mathrm{n}}^2)$size circuits.
2. $\mathrm{O}\left(\mathrm{nlogn}\right)$size circuits.