Assignment 01

Question 1

Answer

1. The algorithm takes $O(a^2)$ steps. The outer loop for $b$ as $a-2$ iterations, and on each iteration it fires another loop for $c$ with $a-2$ iterations. At each iteration we compute a product and check an equality, which takes constant time. So overall the algorithm takes $O((a-2{)}^{2}c)$ steps for some constant $c$, which is same as $O(a^2)$.
2. The algorithm is not a polynomial-time algorithm. While it takes a polynomial number of steps in the value of $a$, it takes an exponential number of steps in the length of $a$, written as a binary string.

Question 2

1. A natural number $a$ is composite just if its 1 or if there are $b,c$ with $1<b,c<a$ and $a=bc$. So that we can construe a pair $⟨b,c⟩$ as a certificate. Specifically:

   • $p(n)$ here is an appropriate polynomial bounding $|⟨b,c⟩|$ whenever $|b|,|c|\le n$.
   • $A(a,⟨b,c⟩)$ is a polynomial-time algorithm that does the following:
     • First check that $a>1$. If not REJECT
     • Check that $1<b,c<a$. This is a constant number of comparisons. If one of these checks fails then REJECT
     • Check that $a=bc$. This is again a constant number of operations. If so then ACCEPT, else REJECT

2. A language $L$ is $\mathbf{NP}$-complete if $L\in \mathbf{NP}$ and $L$ is $\mathbf{NP}$-hard. A propositional formula $x$ is not a tautology just if the assignment $\alpha$ with $\alpha (x)=0$. This is equivalent to saying that there exists an assignment $\alpha$ with $\alpha (\neg x)=1$. In other words, a propositional formula $x$ is not a tautology if an only if $\neg x$ is satisfiable. From here we show that $\overline{TAUT}\in \mathbf{NP}$ by a polynomial time reduction from it to SAT. Namely our reduction is given by the function $f(x):=\neg x$. Now we show that $\overline{TAUT}\in \mathbf{NP}$-hard by giving a polynomial-time reduction $f$ from SAT to it. For this we chose the reduction $f(x):=\neg x$.