Lecture-1
We will be primarily dealing with the lower bounds( time and space) of different problems In this lecture, we shall try to get an overview of this course. We will now have a look at some informal definitions.
P class: Class of problems that can be solved in deterministic polynomial time.
NP class: Class of problems for which a witness can be verified in deterministic polynomial time.
An example of NP problem is 3 colorability of a graph.
Certainly, we can say that $P\subseteq NP$ but we are not sure about their equality.
At present, we have the following diagram.
We are not really clear about the portion $NP \backslash(P\cup NPC)$ where $NPC$ refers to the NP complete problems (They are the hardest NP problems). Problems like "Factoring" and "Graph Isomorphism" lie in this area. However, Graph Isomorphism was proven to be very close to the P class. (Seems like it's solvable in almost polynomial time).
Another problem we face is related to memory efficiency. Though solvable in polynomial time, the problems in P class vary in memory consumption. Take this problem for example.
For a given undirected graph $G=(V,E)$, and for any two vertices $u,v\in V$, we need to check if we can reach $v$ starting from $u$. It uses linear space if we use the "search algorithms". However, it was later proven that the memory efficiency can be improved to $\log n$.
Randomness
The idea of a randomized algorithm is to use the notion of randomness in the machine to solve a problem. Miller-Rabin primality test is one such which checks if a number is a prime. The problems that can be solved using randomness fall under the BPP class. This brings us to the following diagram.
Lower bounds
Just like the upper bound of the complexities of the algorithms, we are also interested in knowing the lower bounds. For instance, for a given boolean formula $\psi$ (Say $|\psi|=n$), we need to check if the satisfiability can be checked in $>O(n^{1.1})$.
Diagonalization
It's interesting to note that $DTIME(n^2)\subsetneq DTIME(n^3)$. Here $DTIME(n^2)$ refers to the problems that can be solved using a deterministic Turing machine in $O(n^2)$. We similarly define $DTIME(n^3)$. It was thought that by using this idea, the P vs NP problem could be solved, however, this idea was crushed using 'natural proofs'.
Lecture 2
A Deterministic Turing Machine with running time $f(n)$ refers to a Turing machine which on taking $x$ as input with $|x|=n$, then the machine halts in $O(f(n))$ time.
A Non-deterministic Turing machine with a running time $f(n)$ refers to a machine that takes $x$ as input and all the paths halt in $O(f(n))$ time.
Considering these, now let's talk about a set of problems.
$DTIME(n^c)$={Problems that can be determined by a deterministic Turing machine in $O(n^c)$ time}
Keeping this definition in mind, we define
P class = $\bigcup\limits_{c}DTIME(n^c)$
NP class = $\bigcup\limits_{c}NTIME(n^c)$
We might now think about, what NP class actually contains. It contains those problems, which contain a certificate to verify, which can be verified by an efficient verifier in Polynomial-time. In formal language,
Suppose $L\in NP$, then there is a polynomial time computable algorithm $V$, such that, if $x\in L,\exists y$ such that $y<|p(x)|$ and $V(x,y)$ is accepting.
Reduction
Here comes the notion of 'easier problems'. Some problems are easier than others and to represent that, we say $A\leq_p B$, which means that there exists a polynomial time computable function $f$, such that $x\in A$ if and only if $f(x)\in B$. In simpler words, one problem can turn out to be a version of another problem. We consider the second problem to be hard.
Cook-Levin Theorem
The Theorem says that SAT is NP-complete.
Configuration of TM: Configuration of a Turing machine gives us all the information about the machine, which includes, head position, current state, and content of the tape.
Computational Tableau: For a machine with a running time of $n^k$, it is an $n^k\times n^k$ table where all the configurations are placed in a valid order.
Proof of Cook-Levin Theorem:
The main idea is to encode the computational tableau in the form of a boolean formula, $\phi$. We will now define a variable $x_{i,j,s}$ where $s\in Q\cup\Gamma\cup \#$. We define the variables as,
If $s$ is present in $(i,j)$, $x_{i,j,s}=1$, else $0$. We will now define the boolean formulas which will lead us to the final formula. Say the input is $x=w_1w_2\ldots w_n$
$\phi_{\text{start}}=x_{1,1,\#}\wedge x_{1,2,q_0}\wedge x_{1,3,w_1}\wedge\ldots$
This enforces the starting configurations.
$\phi_{\text{cell}}=\bigwedge\limits_{0<i,j\leq n^k}\left(\left(\bigvee\limits_{s\in C}x_{i,j,s}\right)\wedge\left(\bigwedge\limits_{s,t\in C,s\neq t}(\overline{x_{i,j,s}}\vee \overline{x_{i,j,t}})\right)\right)$
The above ensures that a cell contains exactly one element.
$\phi_{\text{accept}}=\bigvee\limits_{s\in C}x_{i,j,q_{\text{accept}}}$
This ensures that the tableau is an accepting one.
And finally, we have the most complicated $\phi_{\text{move}}$. We need to ensure that the configuration is followed using a valid transition from the previous step. For this, we just need to look at the immediate top cell of the current cell and the cells on its left and right, and we will scan it through all the $s\in$. If there is no head in the three, we will just have $x_{i,j,s}=x_{i+1,j,s}$. In the diagram below we have marked rectangles. The blue and the red together form the 6-window. The red rectangle is dependent on what there is in the blue rectangle.
Finally, we will have the formula,
$\phi=\phi_{\text{start}}\wedge\phi_{\text{cell}}\wedge\phi_{\text{accept}}\wedge\phi_{\text{move}}$
Lecture 3
Time constructible functions: Suppose we have a function $t(n)$. We say that this is a time-constructible function that is at least $O(nlog n)$ and there exists some Turing machine $M$, which can compute the binary representation of $t(n)$ on input $1^n$ in $O(t(n))$. SOme of the most natural functions we see are time constructible.
Time Hierarchy Theorem: For any time constructible function, $t:N\to N$, there exists a language $A$ which is decidable in $O(t(n))$ but is not in $o(t(n)/log(t(n)))$. In other words, this simply means that if we give a Turing machine more time, it can solve more problems.
Proof:
We will construct a Turing machine $D$. It will accept a word $w=<M>10^*$.
1. The machine will reject if the word is not of the form $<M>10^*$
2. Compute $t(n)$ and set the timer to $t(n)/log(t(n))$. Decrement the timer in every step.
3. If the timer runs out before the computation ends, return reject.
4. If the machine $M$ returns $1$ return $0$ and vice-versa.
Note that $|w|=n$. Now, say we have a machine $M$ which accepts the language $A$ in $g(n)=o(t(n)/log(t(n)))$. Now the machine will take at most $t(n)/log(t(n))$ and say the time taken by $D$ is $dg(n)$ for some constant $d$. Now there exists $n_0$ such that $dg(n)<t(n).log(t(n))$, for all $n>n_0$. Now for every word longer than $n_0$, we will have $M$, returning a value. Now the value it will return will be the opposite of the one $D$ will return. Therefore, it creates a contradiction.
Lecture 4
Space constructible functions
A function $f(n)$ is said to be space constructible if there is a Turing machine that on taking an n-bit input, constructs $f(n)$ in $O(f(n))$.
Theorem: If we have two space-constructible functions $f(n)$ and $g(n)$ such that $f(n)=o(g(n))$, then,
$SPACE(f(n))\subsetneq SPACE(g(n))$
Here $SPACE(f(n))=\{L:L\text{ is decided by a Deterministic Turing machine in }O(f(n))\}$
On the other hand $SPACE(f(n))=\{L:L\text{ is decided by a Non-deterministic Turing machine in }O(f(n))\}$
Savitch's Theorem
Consider a space-constructible function $S(n):\mathbb{N}\to\mathbb{N}$. Note that $DTIME(S(n))\subseteq SPACE(S(n))$. This is because per unit time, 1 tape cell is checked. Also note that the space can be reused.
The Theorem says that $NSPACE(f(n))\subseteq DSPACE(f^2(n))$
Just as a side note, we have, $DSPACE(f(n))=\bigcup\limits_{k}SPACE(n^k)$ and $DSPACE(f(n))=\bigcup\limits_{k}NSPACE(n^k)$
It's also interesting to know that,
$DTIME(S(n))\subseteq NTIME(S(n))\subseteq PSPACE(S(n))\subseteq NSPACE(S(n))\subseteq DTIME(2^{O(S(n))})$
We call the $DTIME(2^{O(n)})$, $EXPTIME(S(n))$ as well.
Note that: $SPACE(S(n))=NSPACE(S(n))$. Another interesting thing is $DTIME(S(n))\subset EXPTIME(S(n))$. This means that there is some strict subset in between, but we are not sure.
Graph configuration
This idea will help us to prove Savitch's theorem. The idea is to consider the configurations of the Turing Machine as nodes of a directed graph and the edges will refer to the flow between different configurations. Say for instance we have a configuration $C_1$ and we have an edge $C_1\to C_2$, then the machine can transform from $C_1$ to $C_2$ legally. For a deterministic Turing machine, we would have vertices with out-degree at most $1$. In the case of a Nondeterministic machine, we would have vertices with arbitrary out-degree. We define the starting configuration $C_{start}$ and the configuration, where the machine halts and returns $1$ is $C_{accept}$. Our aim is to find if it is possible to reach $C_{accept}$ from $C_{start}$. In other words, the machine accepts the word $x$, if it reaches the configuration $C_{accept}$ from $C_{start}$.
On trying this, we may face a problem. At a branch that uses $f(n)$ space, may run for $2^{O(f(n))}$, and each step can be non-deterministic. which may result in a total space of $2^{O(f(n))}$. To deal with this, we will use a strategy. Suppose we are given two configurations and $t$ and we need to check reachability from one to the other using $t$ steps. For doing this, we will have a look at an intermediate configuration and check if it is reachable from the starting configuration. We can then reuse the space to check if the accepting state is reachable from that intermediate configuration. This will give us the space complexity
$S(t)=S(t/2)+O(f(n))\Rightarrow S(2^{O(f(n))})=O(f^2(n))$
PSPACE completeness
Just like the definition of NP-completeness, we have PSPACE completeness. A language $B$ is PSPACE complete if
1. $B\in PSPACE$
2. Every other language $A$ is polynomial time reducible to $B$.
If $B$ merely satisfies the second condition, it is $PSPACE Hard$.
Comments
Post a Comment