Lecture 23 : Part B - Circuits for NP and EXP

IIT Kanpur July 201
20 followers
3 Video Views·Oct 3, 2024
So, there exist v phi u comma v, where u is fixed is a SAT instance, because it is trying
to find this satisfying assignment v. And since we assume that SAT has policized circuits
family C M. So, why not take C M, where M is the size of the instance and give this u and
phi to C M. And now, it will correctly answer, it will answer 1, if there is a satisfying
assignment. And now, let us try to find this assignment. So, C M can be used to in fact,
find a satisfying assignment v. So, how is that, basically fix v. So, first you would have checked
that C M u phi is 1, this you have checked. So, then what you can do in the second step
is fix v 1 to 1 or v 1 to 0. So, now if C M u comma phi v 1 equal to 0, if this is 1,
then we have found, then we have found v 1.
Else, if this falls, then it means that you have to set v 1 to 1, one of them has to work,
both cannot fail. If both fail, then it means that C M u phi is unsatisfiable,
but that step 1 is ensured it is satisfiable. So, next what you can do is, you go with u phi
and whatever v 1 you found out. So, v 1 we will not, we just use what we got and v 2 we can now
play the same game. So, whatever v 1 was fixed in the step 2. So, v 1 was defined here to be
0 or 1 and now v 2 we will try to fix. So, if v 2 equal to 0 works, then else you set v 2 to be 1.
So, now v 1, v 2 both are fixed and you keep going and now you can output the values
v 1, v 2 and v. We did not say how many variables there are in v, suppose it was n,
you can output that.
So, this is a satisfying assignment that we have found. So, this v is a satisfying assignment of
phi u comma v. So, you see using C M, you can actually compute a satisfying assignment.
So, let us call this thing we just did, we can convert it into a circuit and call it C M prime.
So, convert this algorithm into a circuit, call it C M prime.
So, C M prime basically outputs the satisfying assignment. So, C M prime when given
you are writing it as u comma phi is equal to a satisfying assignment v, assignment v
of phi u comma v.
So, it outputs an n bit string, that is the circuit C M prime. So, this means that now we
can write if there exists a v, if this is true there exists a v of there is a satisfying assignment
then indeed we can just plug in, instead of v we can plug in this C M prime and vice versa.
So, if there is a satisfying assignment, then C M prime u comma phi is that,
it works and if C M prime u comma phi cannot give an output that satisfies phi u comma dot,
then it only means that there is no satisfying assignment. So, now you can rewrite psi,
that was for all there exist phi, for all u there exist v phi u comma v, that psi we can rewrite.
So, thus psi is, so psi was what, psi was for all u there exist v phi u comma v is equivalent to
that there exists a circuit C M prime, such that whatever is, whatever u,
string u is given phi u comma C M prime with phi comma u as input accepts.
So, this is the beauty of the circuit, what it has done is, it has flipped for all there exist to
there exist for all, because now this there exist is acting on circuits,
which are not too big, C M prime is only poli size, let me mention that.
So, C M prime is a poli size circuit, which you are looking for, if that exists,
then no matter what u is for all u, phi u comma this output of C M prime
will force phi to accept. So, psi is equivalent to this
and that means, that we have put pi 2 sat in sigma 2, which means that
pi 2 is sigma 2, which means that the polynomial hierarchy collapses to sigma 2.
So, that finishes the proof of Karp-Lipton theorem, that if sat can has Boolean circuits,
then the polynomial hierarchy collapses and there is a nice corollary to this, let us also do that.
So, suppose that something even more drastic happens, exponential time algorithms,
they are all, they all have poli size circuits. So, all the exponential time
solvable problems can be solved by Turing machines with advice in polynomial time.
Then, what will happen, then the same thing happens, actually x becomes equal to sigma 2,
this proof is similar to what we did. So, the idea here is, simulate or check every step,
of the Turing machine, of the exponential time Turing machine. It is any problem,
L in x will have an exponential time Turing machine, look at its steps,
the steps are easy to check and basically, there will be a circuit that can do that,
by using the circuit.
If there is a circuit that exists for x, then every step we will check by that circuit,
thus simulating. So, exponential time Turing machine, let us call it, give it a name m,
thus simulating m by sigma 2. Let us see the implementation of this, how is this done.
So, suppose L is in x and it has a poli size circuit, L has exponential, first exponential
time Turing machine m, assume that it has a circuit also, poly n size circuit C n,
the circuit family C n having polynomial size, computes the j th bit of the i th configuration
of m running on x. So, this is implied by L in p slash poly, we have C n from,
we have C n as L is in p slash poly. That basically, if you want the j th bit of the
i th configuration, any bit of the i th configuration of m running on x, clearly that
is computable in exponential time. And since we have assumed x in p slash poly, sorry I should
say x in p slash poly, since we have assumed that x is in p slash poly, this circuit will exist,
which computes some any bit you want, your favorite bit from the i th configuration.
And now, we can check each and every step of m of x using quantifiers, let us do that.
So, observe that x is in L, if and only for every configuration i and for every bit position
j, this what did we use, C n. So, C n on x comma i comma j to C n x comma i plus 1 j,
this is a valid step of m. So, what we have written here is something obvious, what this
for all i comma j is checking is, every possible configuration to the next happened in the correct
way, following the finite control of Turing machine m given input x of length n.
This can be, this is easy to check, this is in polynomial time,
this can be, this is in polynomial time, because you just have to look at the finite control of m
and what that dictates, like look at the transition function basically,
from there it will follow. So, this can be checked from, easy to check
from the transition function delta m. So, using the transition function, it can be easily checked
whether this is a valid step, we have broken the combination into steps and we have applied for all
operators. So, then m must be accepting
x, so x is in l if and only if m of x is 1, if and only this happens.
Now, all you have to do is, I mean the circuit you do not know, so that we can say using
existential quantifier. So, this means that x is in l if and only if there exists a circuit C
n, so that for all i, for all j this check passes through, that is all.
So, if x is a yes string, there will exist a circuit, such that for all the configurations
which are exponentially many and for all the bits in the configurations,
which is also exponentially many. If you do a check, then the check matches
and since the check matches, it matches that is what m would be doing.
Identically, I mean it is a thorough check of m of x computation and
hence it is equivalent to x being a yes string. So, this means that l is in sigma 2.
So, x is in sigma 2 then and once x is in sigma 2, what happens?
So, everything above sigma between x sigma 2 and x they become equal,
sigma 2 then is equal to polynomial hierarchy, which is equal to p raise to sharp p,
which is equal to then p space and which is equal to x.
So, that was what we had claimed. So, if x has polynomial size circuits, then essentially
none of this to be believed, but it will happen.
So, this is theoretical evidence that x space cannot have polynomial size circuits,
but it is an open question. So, that is open that x is not in p slash poly.
We conjecture that x is not in p slash poly, but we do not know
for sure and obviously, we also conjecture that np is not in p slash poly. So, these are the
famous conjectures and we have shown theoretical evidence for them here.
So, what do we do next? So, Turing machines with advice even they cannot solve SAT.
Let us and they are equivalent to polynomial size circuits. Let us give another interpretation
of circuits, third interpretation if you will and that is to do with parallel computation.
So, Turing machine or algorithm is a sequential way of doing things of solving a problem.
Why is it sequential? Because Turing machine or algorithm gives you
after one step what comes next and what comes after that and so on.
There is no idea of solving many things at once that is what you want in parallel computation.
So, how do we model that properly? That is the question. So, what about parallel algorithms?
Where do they live? Who models them? So, let us define some terms. What do we mean by parallel?
So, a decision problem or in fact, it will not matter. So, any problem function as well.
lengths and in that length all inputs whether x is in L or not or doing this I mean giving
given input x solving the problem L. This L of x can be solved in polynomial in log n time
which is very fast. On input of size bit size n you want to solve a problem in poly log n time
which means you cannot even see the whole input, but what is parallel in this? So, for parallel
we will actually say that the number of processors is many. So, can be solved in poly log n time
by a parallel computer that uses poly n processors. So, this problem L we will say
it has efficient parallel algorithm. If for all inputs of length n as n is growing
you can solve the problem on this input in polynomial in poly log time
and poly n processors. This is important. So, when you talk about parallel computation
you actually want many processors because one processor can do only one thing at a time,
but many processors can do many things and since you have poly n processors they can
look at different parts of the input. They can overall cover the whole input and maybe
together they can solve it much faster and this poly log n is much much faster.
So, you have to note that poly log n which is much much less than n.
So, in terms of the input size the time is much much smaller. So, this is the advantage
of parallel computation over sequential. Is there an interesting example which
can be solved in parallel algorithm fast or parallel computer fast?
So, show that for n bit integers x and y x plus y can be computed in only log n time
if you use many processors. So, by using order n processors. So,
while it will take I mean if you do it just manually by one processor you at least have
to go through the length of x and y. So, that will take order n time by one processor.
So, sequential algorithm will give you linear time, but
parallel computer gives you exponentially lower than that
and this we will next time model via circuit.
