Lecture 24 : Part B - P-completeness and NEXP-completeness

IIT Kanpur July 201
20 followers
2 Video Views·Oct 3, 2024
One easy thing to observe is for P-complete problem that say L is P-complete, then if
that problem is in NC, that is there is an efficient parallel algorithm for a P-complete
problem. What it would mean is that every problem in P has a efficient parallel algorithm.
So, NC will be P. So, if you believe that NC is not equal to P, then P-complete problems
cannot have an efficient parallel simulation. And similarly, P-complete problem if it is
in log space, then every problem is in log space. So, we believe that log space is different
from P and hence P-complete problem cannot be solved in log space. And P-complete problem
cannot be solved in NC, cannot have a parallel simulation. So, in this sense P-complete problem
is hard. It is in the sense of hard to parallelize. This is the meaning of P-hardness. So, let
us introduce it and again circuits will come to rescue. So, circuit evaluation is the problem
we will define. So, circuit evaluation is the problem of given a circuit and an input,
does it accept it. So, is C x equal to 1. So, C is a circuit with n inputs, 1 output and C x is 1.
So, basically circuits with accepting inputs that is what circuit evaluation consists of. It
basically just is asking whether a circuit and an input is 1. So, intuitively you have to compute
the whole circuit for this and we will show that this is P-complete. This is a P-complete
problem. Circuit evaluation is P-complete. So, first is that it is in P. Why is it in P? Well,
because given a circuit you can obviously compute it, given a circuit and an input.
So, given C comma x it is easy to simulate to compute C x by a Turing machine in polynomial
time. Efficiently you can check whether you can compute C of x and then check whether it is 1 or
0. That is the easy part. So, more interesting thing is P-hardness. Why is it P-hard? So,
can you, why can you reduce every problem in P to this in log space using an implicitly log
space reduction. So, let L be in P with Turing machine M of time complexity into the C where
x length is n. So, let in other words let L be a problem which is solvable in polynomial time. C
is an absolute constant. So, polynomial time solvable problem L and Turing machine solving
it. Let us start with this. So, essentially you recall Cook-Levin reduction. That reduction
basically converted every step of the Turing machine computation into logical gates and if
you go over all the steps then ultimately it is giving you the circuit you want. So,
as in just let us recall. So, as in Cook-Levin we can assume M to be oblivious and translate
the step that the i-th step basically which maps configuration C i to C i plus 1.
Translate the i-th step to a formula and this we can see as a constant size circuit. So,
this implies that each step is a constant size circuit. Let us call it C i. So, this is the
major thing we are recalling from Cook-Levin. Once you understand this then now what happens
is Turing machine M has many steps. It has n to the C many steps and every step is just a
computation of a constant size circuit. So, you can join them together and you get a big circuit
still of size polynomial. That is faithfully simulating what M was doing. So, since number
of steps is less than equal to n to the C. In fact, n to the C log n. This means that we get
circuit C of size n to the C log n exactly simulating M. Moreover, this is all fine. This
we understand that Turing machines can be converted into a circuit, but why is it a
log space reduction? That is the only thing missing. So, the i-th circuit C i, this can
be determined using or given can be determined easily. Basically, this is from control of M
and the i-th head position independent of x. That is the point of oblivious. It does not depend
on x. It only depends on length of x, which is n. So, using M's control finite control and the i-th
head position, you can compute the circuit C i given i and the previous configuration C i minus
1. So, taking this as an input, you can compute the circuit and all this only requires. So,
how much space is needed for this? You only need to basically store i in space at most the length
of i, which is what is length of i. So, i goes up to n to the C. So, it is log n. So, what we have
shown is that the problem in polynomial time, which we took as L, this has been reduced to
circuit evaluation on x. L reduces to circuit evaluation. So, you just have to compute the
circuit and if the circuit on x is 1, then x is a string. So, L reduces to circuit evaluation by
log space reduction, which means that circuit evaluation is P complete. So, circuit evaluation
we have shown is a P complete problem, which means that this problem you cannot solve in
parallel. So, this you can now, we can now make this conjecture that circuit evaluation
cannot be done efficiently or cannot be parallelized. So, intuition is that the circuit is already,
I mean although circuit is kind of a parallel algorithm, but for a turing machine to compute
it, it has to go in every part. No part can be, I mean it cannot be distributed across
different processors. One processor has to go through this. So, it is an interesting
problem, which is in polynomial time. It is the hardest in polynomial time in the sense
of parallelization. If you want to convert every problem into a fast parallel algorithm,
then you have to convert circuit evaluation. That will suffice. So, as a corollary what you
get of this from this proof is this problem of circuit SAT. Circuit SAT is the problem
of given a circuit, whether it has a satisfying assignment. Circuit C and there exists an x such
that it evaluates to 1. The circuit SAT is NP complete. Well, this is kind of immediate.
So, circuit SAT is clearly in P, sorry in NP because you have to guess, just you just
guess x and then compute C of x in polynomial time. So, it is clearly in NP and 3 SAT reduces
to it. 3 SAT trivially reduces, trivially 3 SAT will reduce to circuit SAT. So, circuit,
what we have shown is that circuit evaluation is P complete, where the notion of reduction
was implicit log space reducibility and circuit SAT, when this x is not known, you have to
guess it, this is NP complete. So, both these problems are new problems, but they fit very
well with the known complexity, already defined complexity classes.
And circuits also help to understand next to study higher classes like PH, P space.
I mean this even before P space, you have this sharp P. PH is a question about formulas.
So, that is again a circuit question. Sharp P is about sharp SAT, again circuit question.
P space is about QBF and we will now move to next. It also helps to understand next.
So, how is that? So, let us define our next complete problem. Circuits give a natural
problem. For this, I need to define a harder version of circuit SAT. Circuit SAT is in NP.
For next, I have to make it harder. How do we make it harder? We make it succinct. So,
C is a succinct circuit, if given I in binary. So, I is given in binary via n bits.
There exists a polynomial in n time algorithm to output the ith gate. Let us say the ith gate and
jth edge. So, let me make this i, j. So, essentially, what is the ith gate and how
is it connected to its neighbors? So, what is the ith gate and what is the jth edge?
How is it connected? So, this local connectivity information is easy to compute. That is what it
It can be of the order of i, j or n bits. So, I guess 2 raise to order n or order n square.
So, if you look at the number of gates, they are actually 2 raise to n and the number of edges can
be 2 raise to 2n. So, circuit graph or the circuitry is huge, but each interconnection can
be computed efficiently. So, local information is easy to compute. This is what a succinct circuit
is and what we can show the theorem says that succinct circuit SAT. This is next complete.
So, succinct circuit SAT is a circuit SAT, but where the circuit is given to you in a succinct
way. So, local connections can be easily computed. There is an algorithm, but obviously,
the whole circuit cannot be given because it is too large. So, if you can test whether it
has a satisfying assignment, then you can solve next. So, let me point out that
circuit size is exponential 2 raise to order n, but number of variables is n. So, number of
is not exponential. Number of variables is just n, but the circuit itself has large size 2 raise
to n, 2 raise to 2n size. So, whether given such a circuit in this local way, can you test its
satisfiability. So, this problem is next complete. So, first of all, why is it in next? So, it is in
next. It is in next because you can guess x and then you can compute c of x in exponential time
as the size of c is only exponential in n.
So, let me change some things here. So, this is n to the c.
The circuit size is n to the c. c is an absolute constant
and then. So, you can actually guess x in 0, 1 to the n and for this x,
the circuit size is promised to be at most 2 raise to n raise to c for some constant c.
So, in x, it can be any constant c. So, circuits of size 2 raise to n raise to c are allowed,
but the information, local information will be computable in polynomial time,
poly n time. That is all what succinctness means. So, the satisfiability can be checked
once x is given. c x equal to 1 can be computed. So, that part is the easy part.
The difficult part is being hard. Why is it hard?
So, next hardness we will do. We have to reduce any problem in next to that. So, let
L be in next with M being its exponential time verifier.
And input x being 0, 1 to the n. So, we have the verifier, we have the input and we have the
language in M is the Turing machine verifier and L is the language problem in next. Now,
the ith step of the Turing machine c i to c i plus 1 configuration change.
This has, so what will this configuration size be?
This will be exponential. The configuration size is exponential, but
so this small, the smallest change from one configuration to the next,
this is given by M's control. So, that is a constant size circuit, which is producible in
how much time? So, you just have to compare the locations. So, it will be computable in log of
the number of, I mean the basically configuration size
in this time, which implies. So, configuration size is how much? That will be
log of the number of steps,
which is 2 raise to n raise to c, that is polynomial in n.
It is polynomial n times.
So, which means that the configuration graph, so this configuration graph is
I mean or the circuit that you get,
the corresponding circuit is succinct,
which means that we have reduced L to succinct circuit set.
So, every problem in next, where the configuration graph or where this
cook-Levin reduction can be reduced to succinct circuit set. So, this is a problem,
which is next complete. So, with this we finish the course. We covered a lot of topics
and to learn more, you can do the advanced courses. I hope you enjoyed. Thank you.
Thank you.
