Hi everybody, today we're going to continue learning about data structures and algorithms.
Specifically, we are learning about p versus np. So far we've seen a lot of good news like
such and such a problem can be solved quickly that means in linear time or at least a time that is a
small polynomial function. np completeness is a form of our bad news it's going to show evidence
that many important problems can't be solved quickly so first let's define what p and np are
class p problems are problems that be can be solved in polynomial time so that means it can be
solved in a linear time or some type of polynomial function like n squared or n to the cube class p
problems are deterministic algorithms that means these algorithms behave predictably
class and p problems stand for non-deterministic polynomial time a non-deterministic algorithm
uses some type of operations to guess what to do next next when a decision is made
and it can exhibit different behaviors each time it is ran a problem is np if you can quickly
in polynomial time test whether the solution is correct and that means you don't worry
about how hard it might be to actually figure out the solution we also have np
complete mp complete problems are the hardest problems in an np set a decision problem is np
complete if it is np see so we have np and then end compute which means any given solution for
np complete problems can be verified quickly but there is no efficiently known solution
and every problem in np is reducible to polynomial time all np complete problems are equivalent
computationally a problem is np hard if it follows only the second property of what we mentioned
above which means every problem in np is reducible to polynomial time and np complete the np complete
set is a subset of np hard you can also see here that p is a subset of np which means that
any problem that can be solved by deterministic machines in polynomial time can also be solved by
non-deterministic machines in polynomial time there's also another belief that p is actually
not an np and this is a famous open problem in computer science you can actually make a million
dollars if you can prove that p is in np or p is not an mp it's one of the famous million dollar
uh unsolved problems in computer science so if you're feeling ambitious and probably further
on into maybe your phd career you can maybe take up the gambit and try to prove whether p
is np or p is not np so i've talked about p and np and mp complete and mp hard problems
but uh that's kind of hard to grasp right let's talk about it in the sense of example
problems what is a p problem a problem that can be solved in polynomial time would be something like
determining if a string is palindrome that means front to back equals back to front just flip the
two compare them find if a string is contained in another string that's basically searching the
string for the other string you can do that in end time determining if a number is prime
you're going to divide until you you divide by certain factors until you determine if
it's prime or not because it won't be able to be divided right those are set examples that can be
done in polynomial time so now let's look at some example np complete problems now remember
no problem can be np complete without it being np and np hard based off of what we saw before
there are some very famous problems within np complete we have the traveling salesman problem
which states given a list of cities and distances between each of the pair of cities what's the
shortest possible route that visits every city exactly once and then you're able to return
to your original city in this case you have to analyze all the possible routes in order
to figure it out and there's no real polynomial time that they can be solved in so
you can you open up an array of possible abilities and the list of roots is super long
but if you find the if you look at just the solution and then you check if that's right
it's very fast and it's able to be solved in polynomial time the traveling salesman problem
is actually a very famous problem and you'll run across it uh potentially when you're out in the
field working as a software engineer because it has several applications like you end up using
this within planning and logistics and uh just manufacturing different items so this problem
isn't unique to other np complete problems are the knapsack problem which is that you're given a set
of items and each have a weight and a value and then you need to determine each item to include
in a collection so that the total weight is less than or equal to a given limit and the total value
is as large as possible another example of np complete problems is the click problem and this
is a computational problem that involves finding clicks which are subsets of vertices all adjacent
to each other in graphs so there's a lot of different mp complete problems i just gave
three examples but these np complete problems you actually do run across within your career an
example of an np hard problem that is not np is the halting problem the halting problem says
given a specific program and its input will it run forever or halt that is an np crop hard problems
yes no i guess no answer that can only be solved really by putting in the input and then finding
out so why does this all matter well as i said before np complete problems come up all the time
so knowing that they exist and they're hard to solve saves you time to work
on a compromise for that solution so some workarounds are using heuristics
if you can't solve the problem with a good worst case time maybe you can come up with a method for
solving it in a reasonable fraction of a common cases you can solve the problem approximately
so a lot of time the problem comes up with a probabil a probable fast algorithm
and maybe it doesn't solve exactly what you want for your solution but you can make it close enough
you can use exponential times the exponential time solution anyways if you really have to solve the
problem exactly as it is you can settle on the fact that you're going to have to write this
exponential problem in exponential time and stop worrying about trying to find a better solution
or to find a better abstraction it's possible that the np complete problem you're trying to solve
happened because you're ignoring some seemingly unimportant detail that would actually
help narrow it down so i'll give an example in my career i've run across several mp complete
problems one is the traveling salesman problem cto came to me because they wanted to find the
nurse that was closest to a patient so they could travel to their house and administer medicine
so we have a list of hundreds of nurses all over the united states and we need to find the
nurse that's closest to that patient and the line that my cto said was it's not a big deal
it's just a traveling salesman problem which my response was it's famous for a reason because
we have to look at every single nurse so i started asking more questions can every nurse administer
medication to the patient no they have to be certified for certain things so that narrowed
down the list of nurses they have to be certified to work in that state well now we're narrowing
down the nurses that can be in that specific state that the patient is in they also have to be
working on specific days so that narrows it down even more and slowly we brought the problem down
yes still an exponential time but we narrowed the subset down so that it was a lot smaller and then
we're only looking at about five nurses within a city that can help the patient not looking at the
every single nurse within the united states so now you have a better understanding of p
and np problems in our next video you are going to learn about linked lists happy learning