Lecture 13 : Part B

IIT Kanpur July 201
20 followers
Mar 1, 2024
[Music]
[Music]
so that's
1/2 so we have shown that
uh uh Sigma 2 is solvable by NP to the
set ndtm given another ndtm as an oracle
right that's an interesting thing now
the other half is U showing that NP to
the SAT can be written
as
uh there exist for
all so let's do
that so NP to the SAT is in Sigma 2
part let uh L be in NP to the
set decided
by poly time ndtm
n using S
Oracle
so uh this n will make uh
choices right nistic choices and will
also refer to
sat and this whole business we have to
express as Sigma 2
expression right so this we have to do
carefully and we'll obviously also use
cook Liv
here
um so n makes
uh
choices in
its execution
path and
queries the
Oracle on CNF
formulas so the choices uh intuitively
will refer to their exist quantifier and
the
queries uh that analysis will be more
uh will be trickier right because
quaring
um for
sat right the query that is happening is
for
sat sad uh problem so answer may be yes
or
no so yes
will correspond to their exist
quantification and no will correspond to
for all quantification right at
compliment and we have to uh keep track
of that
separately so let's
study an
execution of n on
X okay so
say
and makes uh bit
choices C1 dot
dot
CM so that's the non-deterministic
choice remember in an ndtm in every step
there is a choice which transition
function to use Delta 0 or Delta 1 right
so that is what C1 to CM
represent and uh
say and
queries
start on formulas five
um with these
choices accounted for that this is the
first Formula then second formula and
finally key
formulas and gets
uh
answers
E1 E2 dot dot EK which are
bits right so these are the important
things in the computation in the
execution path of n uh with input
X so the bit choices which were made by
the I mean in this particular execution
path C1 to cm
uh what were the SAT instances queried
that is 51 to 5K and what were the
answers obtained respectively a12
AK uh zero answers will correspond to
SAR for all
quantifier one answer will correspond to
set their exist
quantifier
okay so then what do you
get so now X is accepted it's a yes
string if and only
if if and only if there
exist
choices and there exist
answers
on
which
um n
accepts on the
part C12
cm
and uh A1 to
a are the correct
answers right so X will be
accepted will be a yes string for L and
remember L was uh NP to the SAT to begin
with right so it will be a yes string if
and only if there is a way to choose the
non-deterministic bit C1 to
CM uh and get correct answers A1 to
AK says that with this information this
is the only information n needs
everything else n is
deterministic so given these two things
then n accepts on the path right that is
exactly the definition of yes
string which we can now write in a
different
way if and only
if um so the thing is how do you verify
that even to a are correct answers right
for this we have to go back to the
definition of sat and sat
complement so that's what we we will
do there exists c
bar then there exist this a bar A1 to
a there exist U1 to
UK says that for all V1 to
VK
um so U1 to UK is comes with the I mean
is Quantified by their exist so this
will be used to
check uh those answers A1 to AK which
are
one and V12 VK will be used for those
answers that are
zero let me write it down
here
okay so it's for those
answers to check whether they are
correct or
not so n accepts
X on the path c
bar and answers A1 to
AK
um
and now the verification the correctness
of the answers so that is uh for all I
in
K when EI is
1 when AI is one then there should be
a uh
certifying
assignment okay so UI is the certifying
assignment and the same for all I when
eii is
zero then
five VI is zero
but note that uh VI are Quantified by
for
all right there is a for all on VI so
that's a different
demand so VI is every VI it should come
to zero if the answer AI was Zero while
UI
um is Quantified by their exist
so UI is Quantified by their exist VI is
Quantified by for
all right so that is why two quantifiers
are needed U that is enough to check the
answers and uh finding the path the
nistic bits that for that there exist is
enough there exist c
bar and this you can see is already a
sigma 2 expression so that's what we
deduce so we deduce that
uh L is in Sigma
2 right which means that
n p to the
SAT is in Sigma
2 and we have already shown that Sigma 2
is in NP to the side so they they are
actually equal
now so NP to the SAT is uh Sigma 2 NP to
the SAT is also equal to NP to the n P
by
definition okay so that's the structural
result the structural result says that
Sigma 2
is NP to the sigma
1 and
uh yeah so that finishes the proof
the remaining stuff I leave as an
exercise so
[Music]
uh fill in the
details for I greater than equal to 3
okay this will be identical uh the proof
will be almost unchanged you just have
to
be more elaborate with the
quantification and then by
induction the this will be proven for
All Eyes basically you you have to
design this uh you have to show that
Sigma there is an ndtm which which is
using Sigma I minus
one now Sigma I minus one again has uh
answers query answers can be yes or no
yes will be Sigma i- one set and no will
be Pi IUS one sat okay so sat and sat
complement and then yes no answers you
verify separately as we
did just
before okay so what we have shown
is that Sigma 2 is NP to the n
P Sigma 3 is
NP to the NP to the NP and then be it
becomes hard to write this just a tower
of
inps okay so this is
the this looks pictorially
better then the first definition of
polinomial hierarchy okay this is the
hierarchy keep putting
NP in this
Tower and the open question here
is that
uh NP ra to
NP is
conjectured is is harder
than
NP okay
though P to P is
p so P to P you can show easily is p uh
it's basically because you can negate
within the class P
negate the answer of the query
within poomi time that you are not able
to do in NP to the NP okay you are not
able to actually negate the answer
within NP so it's the same NP Co NP
difference if NP KP are
different then this question is resolved
if NP KP are the same then actually NP
to the
NP yeah so then what happens think about
that
so what
happens if NP is
co okay basically you have shown that PO
collapses to NP so Sigma 2 will
become uh NP in that case so what we'll
do next is uh what
we'll
uh we'll now investigate the space
between uh the poly hierarchy and P
space okay so again we don't really know
whether these two are separate but under
this all this theoretical evidence it's
safe to say that pH and pspace are pH is
proper subset of
ppace
so can we now fill that Gap talk about
that Gap is there something interesting
in that and indeed there is a very
interesting complexity class or many
complexity classes that we can put
there and that brings us to the topic of
counting
okay so let's study the complexity of
counting
problem so the main motivational problem
is sharp
set
so it Maps Boolean formulas to
their number of satisfying
assignments okay so it will map this
function first of all it will Shar set
will not be a decision problem it will
be a functional problem because we want
to count and the function is map F
to the number of satisfying
assignments
so number of satisfying
assignment off
fire okay that is uh what this
functional question is
and as always
the our interest is how fast can you
solve
this so is Shar set efficiently
computable
okay
so what is the I mean we need to define
a complexity class which covers uh
functions instead of decision
problems so P is
for decision problems that can be
efficiently
solved FP will be for functions that are
efficiently
solvable functional polinomial
time
so FP
is f such
that this
function on the Boolean
strings is uh
computable
by poly
time turing machine
MF okay so it's uh similar to P except
that
the um elements we are talking about are
actually functions okay the
uh don't output a bit but many bits
output a
string call it functional polinomial
time and
uh now we formalize the
question is sharp set in FP
so given a Boolean formula can you count
the number of satisfying
assignments in polinomial time by a
deterministic throughing
machine and the conjecture is that you
cannot right if you cannot if you
conjecture that P is different from NP
then you can't
uh
um check
satisfiability so there is no chance
that you can count the number of
satisfying
assignments right even dis
distinguishing Zero from nonzero we
assume is hard so clearly that that's
the conjecture here
also and
uh so the first counting related
complexity class is sharp
P so sharp sat
motivates the
class
short
P which
is
formally defined
as so function
f is in Shar
p
if there
is a polytime touring
machine
M and constant
C such
that for All In
puts what is f ofx f of x uh is the
count of the number of satisfying
assignments of some
entity on the input
X okay so f of x is equal to the number
of satisfying
assignments let's call it
Y which will be I mean which can be
polom longer than x so x to the
C just as a
formality
uh mxy = to
1 so it is counting uh how
many
uh y are there that
satisfy during
machine uh this verifier
M's
computation so it's
also
that so we can write it like this sharp
p is the collection
of
functions that
count the number of accepting
Paths of an efficient
entity
okay so sharp Peak always any any
problem any function in sharp PE has
this property that it's a counter for an
for a poly time
NDT okay so F on X will be the
value
uh in how many ways is the ndtm
accepting
X that's a natural thing although P here
is kind of misleading because we don't
believe this Sharpie to be efficient at
all okay in fact we believe it to have
very hard
problems so this Sharpie is not like P
it's more
like
um collection of NP heart
problems or
harder so anyways we'll see how hard it
is later uh right now let's just list
some immediate
properties so first is that sharp
set is in sharp P why is
that well sharp set was defined uh
as number of satisfying assignments of a
Boolean
formula and a satisfying assignment uh
of five is basically just an ndtm making
choices so that
ndtm um number of accepting
paths is being counted right so that by
definition
is in Sharpie it's a problem in Sharpie
it's a function in shop
p and uh next is
uh even more
trivial uh functions that can be
computed in polinomial time they are in
sharp
P right because here these are
deterministic tuning machines so you
don't even need the Nonet domistic
bits so open question here
is whether FP
is not equal to
shopy okay just like this is the
counting version of P not equal to NP
okay in a way
um
if you want to show that P is not equal
to NP then this also you have to show
this is implied by P different from NP
right because if Contra positive is if
FP is equal to shop
P then clearly p is equal to
NP so this is something that you have to
show if you want to show P not equal to
NP and
uh how is NP and sharp related so
although we feel that NP is much easier
but comparison we cannot do directly
because NP has decision problems sharp
has functions
so um instead we write it like
this so if you are given sharp set
Oracle then by a polinomial Time turing
machine using that Oracle you can solve
sat right trivially so NP is in per to
Sharp and this whole business can be
done in P
space so here we are allowing uh Sharpie
as an oracle so functional Oracle
right and uh sharp set is in P space
because uh in the same space you can
actually just enumerate all the assign
satisfying
assignments so these are the basic
[Music]
[Music]
[Music]
properties
