Lecture 04 : Part A

IIT Kanpur July 201
20 followers
Jan 27, 2024
[Music]
[Music]
okay so last
time we showed that uh halting problem
is is uncomputable that is there is no
tuning machine that can solve it on all
instances and uh this technique is
called diagonalization proof by
diagonalization and uh there are many
other results
in uh fundamental results in
math like Canter's proof of the
uncountability of reals Russell's
Paradox that certain sets don't exist
and gel's incompleteness Theorem that
there may not be proofs of true
statements there may be unprovable
statements so then we started
uh this concept which will be a key
Concept in complexity theory in this
course which is called
reduction
so
basically you can reduce the Hal problem
if you can reduce Hal problem to your
problem
F right then that makes your problem F
also uncomputable that's the idea so and
what does reduction formally means for
means that
uh if you want to compute F on X then
there is if there is a computable
function f Prime that transforms X um
and then if you want to solve in fact
halting problem on a program on an input
X then F Prime will transform it and
feed this as
input to F and the answers will be the
same okay so f of fime x is the same as
halt of X when this happens then clearly
like you have seen in sub routines or
functions in C
programming u f and fime together when
called will solve also
halt right so this reduction means that
halt has reduced to F and hence f is
also
uncomputable that's the conclusion
now we will move to uh bounded resource
okay instead of this uh time
being finite but extremely large for
which you will run the turing machine
now we will restrict the time and the
space and and that will give us
complexity
classes first it will give us P which is
the notion of uh practical notion of
fast algorithms efficient
algorithms and
NP so we only
study computable
functions so for touring machine
M we do note the maximum number of steps
on an input of size
n as this so y maximum
well maximum because uh you want to go
over all the strings of length n so all
the strings in 01 to the N no matter
which string is given the turing machine
will not run more than time of n okay
this is the time complexity but to be
now it is more formal it is in terms of
the input length Okay so we don't have
to worry about uh time complexity being
different for different string strings
so now we are just taking an upper bound
over all the strings of length n
obviously it's a function of n so as n
increases usually time will also
increase so what is that function we are
interested in that right and that is why
we had defined
astics so now we can understand this
function time of n in terms of astics of
n so for
function
T of n let's say think of TN as n
s right or think of TN as 2 to the N so
for a given function T of
n um
collect all the
problems solvable in that much
time
in fact let me just say approximately T
of
n so we are interested in those problems
that are solvable in around T of n
time in a
class and that class
is D time we call it D time
of
TN D time stands for
deterministic time
complexity but it basically means that
there's a touring machine which
can solve a language contained in this
set in time around T of in so formally
it is the collection of L's
languages
such
that touring machine M there exists a
touring machine
M that
decides
L with time
complexity bigo of
t
okay so this is what I meant around T
ofn time it's actually bigo of T of n
time so all the languages for which
there is a touring machine
M solving in this much time is collected
in D time T of n okay that's the first
complexity class you
learn so for example D time n sare will
mean problem solvable in quadratic
time so example D
time
n are the
problems solvable
in linear time right which is extremely
fast this is like just few few scans of
the input and you get the answer and
there are many such problems if you have
done data structures algorithms
course uh you could recall that there
are many interesting
problems for example blit for search
connectivity and so on in graph
Theory which are actually solvable in
linear time so this is DN is the
collection of those problems so as
mentioned
before
um we consider
polytime
fast right so if your your touring
machine runs in time polinomial in N
then we consider it consider it a fast
touring machine this is in contrast to
exponential
time
okay so polinomial time versus
exponential time is fast versus very
slow and this inspires the
definition of the complexity class
P so poly time solvable
problems
are the form the class P which is Union
of D time n to the
c c positive
RS
right
so n
n² or n to the 10.5 or even into the 100
and so on these are all
considered uh time complexities which
are
fast all of them are included in this
class P so p is called
the deterministic polinomial time class
let me give the full
form okay so P stands for deterministic
polinomial time it's a complexity class
it contains those languages hence those
decision problems which are solvable in
time n to the C for some constant
C on a touring machine okay that's the
full definition of efficient algorithms
and efficient
problems now one point which has to be
made here is
uh for practical people this may not be
fast enough especially if C is
large so in in practice in when you
actually Implement these algorithms in
practice poly
time example n to the
10 may not be
fast right a algorithm which runs in
into the 10 time is actually pretty slow
in practice when you actually Implement
on a
computer um so this fast or efficient is
always a subjective thing uh in theory
we call still we continue to call it
fast or efficient because uh as I
already said it we are comparing with
exponential
time okay but in practice you have to
really optimize
things so theoretical algorithms which
are polinomial time
may
not will still need work when you do the
implementation so even worse
uh what can happen sometimes
is n to
the log log
n may be
faster then
n to the
10 okay in
practice so on inputs of
size 2 to 2 to
10 right that's
the so I mean what we say in theory fast
it may not be practically fast and what
we in theory say slow it may not be
practically slow right so n to the 10
may not be Fast N to the log logn may be
faster because the input sizes are
generally uh limited right so on those
inputs maybe there
are theoretically bad algorithms which
work practically well so you always I
mean this efficiency in and speed or
fast and slow uh when we use these terms
it's always
subjective uh but in the course will
always mean polinomial
time okay that's the
definition so we continue to use this
definition because uh historically it
has served us
well
so historically P
has served as a good
abstraction of fast
computation okay just like curing
machines abstract computers so remove
the architecture and other issues
implementation or hardware issues
similarly P abstracts fast computation
and
removes the actual time in
seconds and the implementation details
and the optimized algorithms okay all
those things get abstracted out in P
nicely and then we can study it
mathematically so historically it has
served us uh well so so we'll continue
with
this and uh basically there are many
many interesting examples in
P so what are the problems in
P so there are many many interesting
examples okay lots of
uh uh I mean almost all the Practical
problems they fall in
P so whatever computers are doing it's
generally uh these are p uh algorithms
in P if you abstracted it as a turing
machine it's in
P so okay enough of P these are U I must
have mentioned in
initially so
like graph reachability
arithmetic
operations linear
algebra right
search so all all these things that you
do in practice uh they are all actually
polinomial time
algorithms so what are the hard problems
problems which are not even in P even if
you give n to the 10 n to the 100 time
you cannot solve them what are those
problems let's now discuss them a
[Music]
bit
sum practically
hard
problems
so the first is traveling salesperson
problem also called
PP so this is a practical problem and
it's uh supposed to be hard there are no
polinomial time algorithms known um
since the last five
decades so the problem is as follows let
G be a graph on N
vertices
with edges labeled with
distances okay so it's an edge labeled
graph in
vertices now question is is there a
close
tour
visiting all the nodes exactly
once of length at most
k
okay so this is an optimization uh
problem that you are given a graph which
is basically you can think of cities or
you can in a city you can think of
localities and or houses and so these
are the nodes and between houses there
are these edges which are the streets
they have distances written on them now
the
salesperson or the post person wants to
go
to uh all these
houses in his or her set of
houses uh at exactly once right there's
no point again visiting the same house
so exactly once and it should be a close
tour so it start from one point visit
all the houses and come back in
obviously needless to say um in minimal
distance
uh
traveled so we are abstracting it in
terms of length K so given K the
traveling salesperson the salesperson
wants to find a close
tour of this much length if it doesn't
exist then the salesperson can increase
K and again call this sub
routin so it's an optimization question
right finding the minimal close to
what is that now Boot Force algorithm is
just uh go over all subsets of
edges right but
edges are at least n and then if you go
over all the subsets it will be 2 ra to
n so it will be a very bad
algorithm and that's the best uh
essentially the best algorithm which is
known okay so there are no good
algorithms discovered yet
second is subset
sum so as the name suggests you are
given a
set of n integers
and natural
numbers and you are given
T another natural number so you given n
+ one
numbers and the question is whether
there is a subset of
s summing up to
T so does there
exist subset of
s summing to
T
okay that's the question like before uh
Again The Brute Force algorithm is go
over all the subsets which is 2 ra to n
and check whether the sum is indeed T
okay nothing better than that is
known notice that you can sort the
numbers but that doesn't help much
because uh still T
May uh
pick small numbers big
numbers middle numbers and sum up to sum
up to T right so sorting doesn't seem to
help and then you don't know what else
you can do with
numbers third
is integer
programming so what is programming where
well programming word comes from linear
programming if you have
seen uh that concept before so linear
programming is the problem of solving
linear
um system where there are also
inequalities okay equalities
inequalities both are there and such a
linear system you are given you want to
find a
feasible point a
solution so that's a famous uh problem
again in optimizing
ation but there they want to find a
real um feasible Point real
valued in integer
programming you have to find an integral
solution and that seems to change
everything okay linear programming can
be solved efficiently there are famous
algorithms known integer programming is
still uh no algorithm known except root
Force so given
[Music]
M linear
inequalities in M
variables is the a
Boolean in fact you can even ask about a
Boolean feasible
Point does there exist a Boolean
feasible
point so uh since I'm only asking for
Boolean feable point you can there are n
variables so you can fix 01 that's two
to in possibilities and see whether this
point is
feasible so that's the brute force and
nothing better is
known so these Brute Force algorithms
you can check as an
exercise so 1 2
3 are
solved
are easily solved in
time uh first
one traveling salesperson it's
uh yeah it's a bit harder than I said
it's not just subsets but also the order
will matter which house you visit first
which second and so on so it's actually
a matter of permutations so that gives
you n factorial time
complexity uh you can think of it as
just going over the permutations of the
vertices right the
houses whether you visit the first which
is the first house which is the second
house third house so on so you can look
at all the
permutations and if there is a close to
or one of these will work so that's a
search in the N factorial
case second is uh 2 ra to n it's about
subsets and third is again 2 ra to and
time
respectively right so work out these
Brute Force
algorithms but these are all very very
very slow algorithms these are
exponential time algorithms
because uh if you take n to be
100 right just 100
houses it's uh not realistic in practice
and the how number of houses will be far
more than 100 but even with 100 this is
giving you 100
factorial so it's impossible to solve
this this algorithm will never
stop right it's an
exponential search space and that's
that's always a
problem you don't want to get stuck in
in exponential search
space so yeah this uh inspires or these
[Music]
problems these are all practical
problems uh from real life and they
exponential time we don't know how to
solve
them so so these problems Inspire the
exponential time
class so exp we call
it this is
the uh D time so time
complexity 2 ra to n ra to
C okay so instead of n to the C now you
are talking about 2 ra to n ra to C and
that's exponential time so these
problems the problem problems 1 2 3 they
are all in
X and we don't know any
better okay so th those Brute Force
algorithms are the best we know so
notice that n factorial is smaller than
2 ra to
n² so clearly
uh D time n factorial is contained in
X and similarly D time 2 ra to n is also
contained in subset of X so these
problems are clearly in X but we don't
know anything better and we would like
to know better because these are all
very useful problems these are not
artificial
problems uh they all have U connections
to combinatorial optimization so these
problem problems have one thing in
common that uh if somebody gives you a
solution you can verify
it right so if somebody gives you a
close T salesperson can
verify whether this close T satisfies
the properties and length is less than
equal to
K if somebody gives you a subset you can
test whether the subset sums to T and if
somebody gives you a Boolean feasible
point you can Boolean point you can
check whether it's Fe
reble right very efficiently it's
trivial to do those
verifications so these verifications
protocol are
uh they are it seems trivial but
actually it's an interesting feature of
these
problems and uh we'll collect those
problems in exp which have this
feature and give it a name
so they have
a common
feature given a close
tour a
subset or a Boolean
point it can be
verified whether it's the right
one whether it's let's say
correct in a short time
time or buy an easy algorithm let me
say so this uh brings us to the concept
of polytime verifiers polytime
verification so this motivate
did cook and
leaven to study all the
problems
that have polytime
verifiers okay
so these problems we
collect in a special complexity class
which we call
NP so language
L obviously Boolean language decision
problem is in
NP if
there exist a
constant
[Music]
and a poly
time or let me say now touring
machine such
that
for all
X for input
x x is in
L uh if an only if so basically yes
strings of your decision problem L if
and only if there is a
certificate U which is not too
large
okay this is where C is being
used the certificate U could be uh
bigger slightly bigger than the input
length but not too much only up to a
polinomial
blowup and then M can certify it verify
it okay so M here is the
verifier checking the
checking whether given you
is correct solution or not
[Music]
[Music]
okay
[Music]
