Lecture 08 : Part B

IIT Kanpur July 201
20 followers
1 Video View·Feb 10, 2024
[Music]
[Music]
so in case h is H is a we take H to be a
growing function and then look at this
padded
set so this is uh not NP hard it's not
as hard as NP hard the reason is that uh
if it was then u a SAT instance s is
being reduced to a pared SAT instance 5
is 0 1 to the 5
H5 and it can't be too big so it size
into the C for constant C now when you
look at the size bound into the C you
get that then five has to be extremely
small so in other words what's happening
is that s of size n is being reduced to
a much much
smaller sat instance so which means
that s reduces
to F of
size small of
n so which means that on repeating
this let's say around end
times many
times we
get CNF
to of constant
size right so s will reduce to five and
then 5 2 53 dot dot up to T here up to
to where T will be constant size so then
it will become a trivial problem to
solve so which will mean that sat is in
P can that happen well we have assume P
to be different from NP so that is a
contradiction right so this
contradiction
means that uh sat h is not NP
hard so that finishes our first
observation so padded set we have shown
is not NP
hard and to prove ladner's
theorem Our intention is to show that
sat H is is in NP minus P so we have
shown it's not NP
hard
um it
be obviously it is in
NP the only thing remaining is it's not
in
P right so can it happen that sat H is
in
P so to deduce that sat
h
is not in
P so this requires uh balance on the
opposite side right so we have shown in
the previous observation that sat H is
not as hard as NP hard but then it
should also be not as easy as
P so we have to make it slightly harder
so for that H should be not too
large okay it should be somehow small
small so we
Define
H in a
way so
that it grows very
slowly first of
all
and
allows a diagonalization
argument okay so somewhere a turing
machine negation has to
happen and this will be a polinomial
time touring machine negate the answer
so let's define it that way
so h of
n is the smallest
I such that for all
X of length login or less binary
strings MI
accepts X in
time I * x to the
I if and only if x is padded
set right so this is a this looks like a
complicated definition but all we are
saying is that this I we are defining as
h of n where I is actually the exponent
in the time
complexity okay time
complexity uh of
what of paded
set right so this is a kind of a cyclic
definition paded set will be defined
once we have H but now we are using
paded at to Define H
itself uh but the reason it will be fine
is because
uh here we are using in length Okay
so we are defining
hn
by looking at the initial part of sat H
the strings which are very small so this
is a recursive
definition and if this MI uh doesn't
exist okay this tuning machine
descriptor also running in time x to the
if it doesn't
exist then you just Define hn to be log
login so
if there does not
exist such an
I
then Define h of n to be log
login so either there is a touring
machine descriptor below log login or
you just call log login as your function
so either way you see that hn is
expected to be a growing function but
very slowly growing it's like log
login and it also will allow
you uh diagonalization tricks
because
uh it's actually using this touring
machine
descriptor okay hn is kind kind of a
touring machine
descriptor that solves padded
set in polinomial
time well I shouldn't say pomal time in
uh yeah
this very small exponent like log login
so
now hn
is computable
in hn is easy to compute let me just say
that
why again because the strings involved
are very small they are only login so
login length so their number is only in
so you can actually um and the
possibilities of I is also very small so
you can actually go over all these um in
an exhaustive
way okay I can be looked for
exhaustively
so how many
eyes so number of eyes
is log log n
times number of
x's is uh
T to
login and
uh it's not really 2 ra to login let me
increase it a
bit Times
login times uh time of MI
how much is
that time of Mi is uh
roughly x to the I right so that is
length is
login and exponent is at most log
login and then to solve sat
because you want to check whether this x
is in padded
set so set so time complexity of set let
me just
say that's 2 to login
again so if you calculate
this this will come out to be
uh
n another n just n squ it's smaller than
n Cub
definitely okay so it's subcubic almost
quadratic time you can compute H ofn
it's easy to
compute so now we can show that sat H is
not in
p
for this
age okay with this this this definition
of h uh the paded set is not in
polinomial
time and uh once we have shown
that if we can show that H tends to
Infinity then with the first observation
we'll have a complete proof of
our theorem ladness theorem so let's
first show that sat H is not in p
let me call it claim one let
yeah that's this for this age set H is
not in
P suppose it is so
suppose turing machine
M solves
setage in
time
C and to the
C obviously constant
C so then what do you do so as is now
usual with the
diagonalization
proofs we'll pick a descriptor of
him let's say
G and argue with that so
pick
descriptor J which is a number larger
than
C such
that m is
mg pick a large enough descriptor of
this during machine and now let us go
through this definition of
AG so what we have is that MJ
decides sat H in less than into the J
time which means that by the definition
of H hn has to be less than equal to
J right that's how we are Define
H sat solver its descriptor should be J
and the expon component should also be
less than
G or in fact we give more it's the same
descript the descriptor should be in the
exponent so x to the I so by that hn is
less than equal to
G and uh L than equal to J for
all n greater than 2 to 2 to J for large
enough n
right that was in the
definition for large enough n
uh this happens each of n is less than
equal to
J so this means
that set H
is just
sat padded with
how many ones 1 to the end to the
G that's all there is to sat AG it's
just sat instances and then you are
padding with
these uh at most in fact and the
j1s and since uh J is a constant this is
just a polinomial blowup in the
complexity so if you can solve sat H
then you can solve sat
so you get that sat is in
P right which is a
contradiction which means
that sat H is not in P to begin
with right so this definition of h is
good
uh it puts at H pit at outside p uh
but then it could be it's possible that
it's very hard maybe it's NP hard so we
have to go
back right we we would have we would
know that sat padded sat is not NP hard
if we can show that H is
growing so does this definition give us
an H that
grows that's our claim to it
does so h n tends to
Infinity
how do you show that age
grows um see by the definition of AG uh
growing growing would mean that
uh in some sense sat
H should not have a polytime algorithm
right so this again falls back on claim
one so actually claim one gives you
claim
two
so sat
H not in P
implies that for all I there exists an X
such
that Mi
cannot
decide whether X is in padded set or
not in time
okay since there is no poly algorithm so
there cannot be a
machine which can solve it in time x to
the I for any constant there'll always
be be a string which will take more
require more right more
time so what does that mean it means
that hn cannot be I
so this means
that hn is not equal to
I for all n greater
than this x so let me use a maybe a
descriptor here uh sub subscript here so
let's call this X suby
and for this x of Y we
get okay so taking n bigger than
that disallows hn to be to be
I in fact it disallow
uh it means that hn has to be bigger
than
this hn can't be I or
less so this means that
hn takes a value
I only
for finitely many
n
right
so because for any I after a certain
point hn cannot be I it will be bigger
which means that hn tends to
Infinity maybe I use this not equal to
that's the simplest thing you deduce
from the previous statement yeah and
then
uh
which means that hn tends to
Infinity okay so that's claim
two and uh
hence so by claims 1 and
two
we
have a polytime
function each such
that sat
H is in
NP not n p and not
NP
hard right all these properties are now
true for this
H and this H is easy to compute that was
also important actually that's important
to put uh sat H in NP
actually I should have maybe set it
here
okay since H is not a
complicated function so
um given an
input you can easily
check in polinomial time you can check
and uh yeah so it's in NP it's not in p
and and because hent tends to
Infinity it's not NP
hard that finishes ladness theorem so
now once we have seen all these proofs
you may
wonder if diagonalization is so smart
such a clever technique can it prove P
different from
NP
can it
prove P different from NP and let me say
can it alone prove without using any
other
Innovation okay maybe if you use many
other techniques then uh it helps but
just using diagonalization type of
arguments
is it will it suffice will it be strong
enough to show P not equal to
NP and uh so to answer this we will
study
oracles so this Leeds us
to this leads us
to the concept of
Oracle so Oracle and relativizing
proofs so one dire direct
motivation for oracles is
um suppose
you have
solved a heart
problem like
sat or
halt by using an alien
machine okay some alien came from some
other planet with a very powerful device
that humans have not built yet which can
solve halting problem
or satisfiability which is much easier
than halting
problem let's say it solves it in
polinomial
time so which problems can you now
solve
okay using that alien device what other
problems could you
solve so uh this actually gives
you a new way of defining complexity
classes so this yields new complexity
classes and let's see the
definition so we call
uh called touring machine
o touring machine m u and Oracle touring
machine using a language
o
if M
has three special
States so a query
State yes or
no
so what will happen is that the way
touring machine can use an oracle for
example this alien
device is
it'll put on the work tape the string
Y which it wants uh o to solve Oracle to
solve and go to state q
query the Oracle will immediately solve
it and then the turing machine will
either go to state Qs or q
no okay if the string Y is a yes string
then yes State otherwise no state so in
one step the problem is solved no matter
how hard using this
Oracle in fact we can take we can
introduce an oracle tape so special or
Oracle
tape
in addition to input tape work tape and
this is the third Oracle tape such
that so that M
enters or if uh
M enters in
uh
state q
query with Y on Oracle
tape
then
in The Next
Step the state
is
Qs respectively q
no if Y is in
O respectively Y is not
in
okay so we'll develop this more next
[Music]
[Music]
[Music]
time
[Music]
