Lecture 14 : Part A

IIT Kanpur July 201
20 followers
3 Video Views·Mar 1, 2024
[Music]
[Music]
so last time
we started uh defining complexity
classes to capture
counting right so the primary counting
problem is sharp
setat which is is uh a functional
problem so it takes a Boolean formula
and it outputs how many satisfying
assignments there are of this Boolean
formula
f um and to capture uh efficiency in
functional efficient functional problems
we Define the class
FP which is uh collection of functions
F that are computable by polytime
touring
machines
and the open question is sharpet is not
in efficient Le solvable
functions so this class defines its own
uh this problem defines its own
complexity class
sharp so that is U those
functions which uh have a turing machine
whose kind of number of uh accepting
Parts they count okay so if you think of
MX comma y as a
ndtm and Y is the as an accepting path
so how many accepting paths are there
number of y's that is
the uh that is what F ofx
computes so this uh sharp set is in Shar
p and it is supposed to be a hard
problem so Shar p is supposed to be a
class harder than that uh harder than
NP it clearly contains FP and uh given
that you can solve NP and you can solve
it itself in PS space in the same space
you can do
counting so let us now move
to a new class that comes out of
shopy so shopy
has an
analogous uh decision
version
which is
PP so language l in
PP uh language L will be put in the
class PP
if there exists a poly
time during machine m
and constant
C such
that for all x uh for all input x x is
in
L if and only if the number of accepting
paths
such that mxy is
1 so PP stands for
probabilistic uh polinomial time and
what will happen here is the number of
accepting paths will be more than half
or at least half okay so amongst the
paths at least half of them are
accepting when that happens happens then
we say then X is a yes string okay if
and only if so such problems which are
solvable by this uh you can think of it
as
a for now as a probabilistic touring
machine with probability half it accepts
and less than half it uh
rejects so there is
a minuscule advantage that it is giving
to the Y
string which is half
so function in
PP
computes the most
significant the most significant bit of
the corresponding
function in sharp
P okay that's the first
observation we can make that a Boolean
function Boolean function in
PP let me add Boolean here that's
important so Boolean function for
example this langage L uh this is in PP
so it means that you are able to compute
the most significant
bit right so basically if you see in
binary the number of accepting parts
then the most significant bit is one if
half of the paths are accepting
otherwise it is zero and that is
what uh defines
PP
so we will now prove some interesting
facts that actually PP and sharp are in
a way
equivalent so what we'll show
is shop
Set uh sharp set can be solved using p
as an oracle okay so if you can compute
the most significant bit then using that
as a sub routine you can actually
compute the whole string giving you the
count of accepting Parts okay that's uh
that's an interesting consequence and
hence it would imply
that if you can compute sharp P then
using that Oracle like like sharat
Oracle you can solve
PP okay so to a polom time machine
sharpy Oracle is equivalent to PP
Oracle okay so in that sense PP and
sharpy are kind of
equivalent
okay there is this kind of equivalence
in Computing the most significant bit
and the whole string of the
count so the key thing is to show the uh
First Property which is how do you
compute the number of satisfying
assignments if you know that the
assignments are satisfying assignments
are at least least
half so let five be a Boolean formula
given in the input in variables X1 to
xn
so using
PP we
know if uh the number of satisfying
assignments of
five okay this notation will mean number
of satisfying
assignments is uh greater than equal =
to 2 nus
1 or
not okay so we we'll be basically able
to compute the MSB of uh number of
satisfying
assignments um so since it's in N
variables half is 2 to n minus 1 but
then from this how do we actually
compute this
uh uh sharp five
right this is just one bit how do we
compute the other bits somehow we have
to fill this difference right this
unknown unknown difference between 2 to
n minus 1 and sharp 5 so for that uh let
us Define the difference as
K so the idea
is
um to
find the minimum non- negative integer
K such
that
k+ K plus number of satisfying
assignments is 2 to
n at least 2 to n right so greater than
equal to but since we are saying minimum
K It's actually an
equality
using
binary
search
and N
+1 non-deterministic
bits okay so we'll compute the
difference uh using binary search and
many non-deterministic
bits uh so with that
uh what we would have shown
is that
uh uh using
PP uh we have solved Shar set in
deterministic poal time okay base
machine has to be
FP so consider uh
ndtm m
that on input
F and
K
uses non-deterministic
bits y0 to YN
as
follows so on y 0 equal to
1 M
guesses
y these n Bits it makes this guess and
outputs 5 Y
Bar so basically on uh it is just
guessing a satisfying assignment right
it will be one output will be one if and
only
if um a satisfying assignment was
guessed
otherwise so this is kind of point
number one or step one is is the part of
uh hash
F right you can think of this as step
one and the step two will be
corresponding to
K and that's so that the sum comes out
to be 2 to n so on y0 equal to
0
M
accepts exactly K
strings Y
Bar that's the key part right so y 0al
to 1 is covering U hash F and y0 equal
to 0 is covering in
K and
uh so total number of accepting paths is
by definition 2 to n so let's write that
down so number of accepting
paths number of accepting Parts uh of
M 5 K
is k
+ this this is by definition the way it
is accepting right while the possible
paths this is
exactly uh all possible values of y0 to
y n which is 2 to n +
1 right so um so we have basically made
uh 2 to n half of 2 to n +
1 okay in this by this orange definition
we have an ndtm where if the number of
accepting paths is half or
more that will be enough
to compute k
so but you have to start with a k so
basically the idea is that you uh guess
K and then verify it by using PP
Oracle okay to do a binary search and by
that
uh in around n iterations you will be
able to find the right value of
K so K plus the number of assignments
satisfying assignments greater than
equal to 2 to n
this can be
learned by
quering the pp Oracle
On
5K okay so you can start with k
uh uh let's say one check this by PP
Oracle if this is false then it means
that you should increase K so Double K
which is
two if this also fails then you go to 4
k = 4 and so
on
so so find K
Min so starting
with k to be 1 then two then 4 then
8 and
ultimately key maximum can be 2 to n try
all these n+1 possibilities so find K
Min from MSB to
LSB bit by
bit each using
a query to PP
Oracle so in n+1
calls in at most uh n +
one calls to the
Oracle we find
we find
kman and so it means that we have
computed the number of satisfying
assignments
right
so once we find K Min then the
difference gives us the number of
satisfying assignments so that is this
is just an FP computation right with n+
one Oracle calls to a PP problem
like
U the hardest problem in
PP so if you can solve PP then you can
solve uh
uh shop
set th uh shop
set is in FP to the
pp so that's a nice
uh reduction from shops uh of pp
to of sharp set to
PP and uh the second proposition is now
immediate okay so how do you do
that let's solve
that so we have already
shown that
uh P to shop
set is contained in
P to PP right if you can solve PP then
making those calls you can solve sharp
set and so any
problem that
is uh calling sharat as an
oracle those calls can be replaced
by uh PP Oracle calls so P to Sharp set
is in P to
PP and uh but you wanted to show an
equality in fact the same proof
shows that for any problem in Shar
p p to L is in P to
PP well this is because we didn't really
use sharat's specific
properties
right you can do the same thing with
the any problem in sharp
so for any sharpy problem l p to L is in
P to
PP and what does this mean this actually
implies that P
to Shar p is in P to
PP every call can be replaced by a PP
Oracle
call so we have shown both
ways while P to
PP is trivially in P to shop
P okay P to PP is in P to sharpy because
well if you have sharpy
access you have access to all the bits
of the count so you obviously can also
compute the most significant bit so that
is Trivial which means
that P to PP is p to
Sharp okay so that finishes uh this
equivalence so again we started with uh
functional complexity class sharp we
ended up showing that it's actually
equivalent to a decision to a normal
complexity class which is PP and uh now
we will investigate Shar P
further okay sharp actually has complete
problems so let's investigate
them
so call
function
f shopy
complete
if first of all it should be
in shopy
itself
and every problem in shopy should reduce
to this function
so
shopy is should be
in FP given
F okay so this is a nice way to say that
every problem in sharpy reduces 2 f
basically sharp should be a subset of
functional efficiently
solvable functional problems using f as
an
oracle so this is called uh sharpy
hard so what this is saying is that f is
sharpy hard if it is also in P Shar P
then it becomes sharp P
complete this thing by the way is also
called uh Turing
reduction so this is also the notion
of Turing
reduction okay in contrast to the car
production we saw so here actually sub
routine calls are being made
so whatever you can solve
by uh calling f as a sub routine so
there will be many calls possibly for
normally many
calls uh so using this if you can solve
a problem G then you call
it a turing reduction from G to F
suppose G is
here
then notion of tuning
reduction of G2
F okay this is
the this is more um this is much more
powerful than car
production now from this
uh
reduction or the or the completeness
notion shopy
completeness what you can see trivially
is if a Sharpie complete problem is in
FP so f
is sharpy
complete and F is in
FP
then
FP
is sharp
P because uh if you can already solve F
in functional uh polinomial time then
functional polinomial time calling
functional polinomial time as an
oracle is still functional polinomial
time okay just because of that sharp
will be inside FP that's the simple
proof
and uh what is a sharpy complete
problem is there a natural problem that
is Sharpie complete so we have been
looking at sharp set and that happens to
be Sharpie complete follows from cookle
directly
so shop
set is shopy
complete uh so we
know that shop
set is in
shopy
and now we have to show that it is also
Sharpie hard every problem in Sharpie
should reduce to
this in the above sense right Turing
Turing
sense and
let let
G be in shop
p with uh
corresponding so G is Computing uh
number of accepting Paths of a ndtm
m so since
uh M's
computation can be converted to a
Boolean
formula okay M's computation can be
converted to a Boolean formula by cook
Len so what it means is
that uh for all input
X this uh G of
X is equal
to number
of accepting
Paths of M on
X which is also equal
to
[Music]
um so let me call the Boolean formula
five which is also equal to the number
of satisfying
[Music]
assignments right which implies that
g is in FP to the shop set
so think of cookle reduction as
a efficient uh function which it
is it was just quadratic blowup and then
you can make a sharp set
call right and once you have the sharpet
call you will know
um the value G of
X so this you know since G was any in
shop P it means that
shopy as a whole is
in FP to the shop
set and
now so that's
hardness sharp set is sharpy hard and
hence it is
complete
yeah so that gives a pretty good
understanding uh of Sharpie we
have a complete problem of Sharpie we
have a Boolean version of
Sharpie and what we'll do next is
something even more brilliant which is
an algebraic formulation of
Shar
okay
[Music]
[Music]
[Music]
