The primary topics in this part of the specialization are: shortest paths (Bellman-Ford, Floyd-Warshall, Johnson), NP-completeness and what it means for the algorithm designer, and strategies for coping with computationally intractable problems (analysis of heuristics, local search).
Definition and Interpretation of NP-Completeness I
Loading...
Del curso dictado por Stanford University
Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
389 calificaciones
De la lección
Week 2
NP-complete problems and exact algorithms for them.
Conoce a los instructores
Tim RoughgardenProfessor
Computer Science
We now arrive at the heart of the discussion, the definition of the
complexity class NP as computational problems where you can efficiently
recognize the solution, roughly the same thing is problem solvable is in good
force search. The idea of NP completeness, that the problem can be as
hard as any other problem, where you can efficiently recognize a solution, the
ubiquity of NP-complete problems, including possibly a problem you're
working on right now in one of your own projects, and what should be part of your
toolbox, a simple recipe for proving that problems are NP-complete.
We left off the last video noting that the travelling salesmen problem by virtue
of being solvable in the exponential time using brute force search is certainly not
as hard as notorious problems like the halting problem.
So, perhaps we can instead of mass evidence of interactability for the TSP
by showing it's as hard as any other problem solvable using brute-force
search, that is every other brute-force search solvable problem reduces to
solving the traveling salesman problem. To turn this idea into mathematics we
have to identify the minimal ingredients necessary to solve a problem using brute
force search. And the key idea turns out to be the
efficient recognition of purported solution.
[SOUND] Specifically, we say that a computational problem,
like, say the traveling salesman problem, or frankly almost any other problem we've
talked about in these classes is a member of the complexity class NP if it meets
the following two criteria. The first property is sort of a simple
prerequisite. It is search that solutions have length polynomial in the input size.
The second property, and this is really the key one, is that if someone offers up
to you a purported solution to a NP problem, you can verify its correctness
in polynomial time. To make sense of this abstract
definition, let's think about some concrete examples.
Let's start just with the traveling salesman problem.
So, consider the instance of the traveling salesman problem that's
specified by some n vertices and distances amongst all of the pairs of
vertices. And suppose we want to know whether or
not there's a tour that has a total length.
At most one thousand. So, let's for the moment set aside the
problem of checking whether or not one of the n factorial tours does indeed have
cost of at most 1000. Let's instead think about the much more
modest question, of whether or not a single proposed tour has cost at most
1000. Well, that computational problem is to
verify whether or not a single suggested tour meets the target or not.
That's an easy computational problem, right? The tour is specified just by
order in which you're supposed to visit the vertices.
The length of that ordering is certainly polynomial in the length of the input,
and all you gotta do is add up the n edges that gets traversed in this tour,
and check if this sum is at most 1000 or not.
This argument shows that checking whether or not there exists a tour, with total
cost and most sum threshold, does indeed belong to the complexity class NP.
Right, you can write down a purported solution, in polynomial length. All you
need to do is specify the ordering, and you can verify whether or not a candidate
solution, whether or not a proposed tour meets the threshold in linear time, just
by adding up the corresponding edge costs.
If it bothers you that I moved away from the problem of computing an optimal,
minimum cost tour, and studied instead the seemingly easier problem, I'm just
checking, does there exist a tour that has total cost at most a given threshold,
notice that the former problem reduces to Multiple indications of the latter
problem, just by binary search over the threshold.
The same reasoning can be applied to pretty much all the computational
problems we've seen in these courses, placing all of them into the complexity
class NP. So for the types of problems we've been
thinking about, solutions can generally be specified in linear space, correctness
can be verified in linear time. Another genre of problems that we haven't
really discussed in these classes, but are important in the application domains,
and are also canonical NP problems are constraint satisfaction problems.
In general in a constraint satisfaction problem you have a bunch of variables.
The simplest case would be binary or Boolean variables.
And then you have a list of constraints, and each constraint specifies for a
subset of the variables. a permitted list of configurations of
those variables. So one simple case which some of you've
seen and if you study NP completeness property you'll definitely see it will be
the three set problem. The three set problem does indeed
consider Boolean variables, so each variable xi can either be zero or one and
you can think of the clauses as forbidding a single assignment to a
triple vertices. So a clause might say you are not allowed
to simultaneously assign. X3 to 1, X5 to 0, and X8 to 1.
So clauses for big particular triples of assignments, and the question then is,
does there exist an assignment of all of the variables to 0 an 1, that
simultaneously satisfies all of the constraints.
These kinds of constraint satisfaction problems also belong to the complexity
class in p. So here if you have a purported
assignment of all of the variables to values that meets all of the constraints,
well you can write it down very simply just the value for each of the variables.
And it's easy to check. I just iterate through the constraints
one at a time and see if yes indeed, the values that you're suggesting for the
variables in that constraint are on the list of permissible value combinations.
At the beginning of this video, I suggested that the complexity class NP
would represent problems that are brute force solvable, in the same way that the
traveling salesman problem is. If you look at the actual definition I
just gave you of the class NP, it's in terms of efficient recognition of
solutions, but let's now observe that this definition NP, in terms of efficient
verification of purported solutions does indeed imply that these problems can be
solved in exponential time using brute-force search.
So really, all you do here is check each of the candidate solutions one at a time.
And in doing so, you see very clearly the role of the two properties in the
definition of an NP problem. The role of the first property saying solution length
has to be a polynomial in the input size, in turn, restricts the number of possible
solutions, the number of bit strings of that given length,
to be at most, exponential in the input size.
The second property of course assures you that for each of those only exponentially
many possibilities, you can verify whether or not it is a correct solution,
whether or not it's a short TSB tour, whether or not it's a satisfying
assignment to some variables in a constraint satisfaction problem in
polynomial time. Now because the requirements for the
class NP are so weak, the class NP is very big, where all
membership in NP requires essentially as the ability to officially recognize the
solution. You know one when you see one,
and as you can imagine, that property is met by many of the computational problems
that we ever think about. Factoring almost any graph problems you'd
ever think about, sequencing problems, most constraint satisfaction problems,
and so on. As we've said, it's true that not every,
natural computational problem, is NP. The halting problem is an extreme example.
That's in fact undecidable, there's no algorithm at all. There's also some
natural problems and some application domains which are neither in NP, nor they
undecidable. So, model checking is one domain that
furnishes lots of examples of problems strictly harder than NP.
The vastness of the complexity class NP means that NP-completeness is strong
evidence of intractability. Remember what it means for a problem to
be complete. For some set of problems, it means it's
as hard as any other problem in that set. Every other problem in that set reduces
to the complete problem. Therefore, suppose you had a polynomial
time algorithm for just one, NP-complete problem,
you would get, automatically, by the definition of a reduction, a polynomial
time algorithm for every single computational problem in NP.
Every single problem for which you can efficiently recognize a solution.
That is, solving just 1 NP-complete problem in polynomial time would imply
that NP is the same as P. Every problem in NP can be solved in
polynomial time. It's pretty hard to really grok all of
the ramifications of this kind of result, if P were to equal NP.
So, just as one example, modern e-commerce, as we know it, would
fall apart like a house of cards. That's because it depends on the security
of crypto-sysytems, like RSA, which in turn assumes the computational
intractibility of problems like factoring.
Yet, an efficient algorithm for even the most obscure NP-complete problem, would
automatically imply, imply, at least in principle, a polynomial time algorithm
for factoring. So this provides a satisfying resolution
to a narrative we began in the previous video.
Recall, we were discussing the traveling salesman problem.
And, like thousands of other people, we were wondering whether or not there was a
polynomial time algorithm for it or not. For example, Edmunds conjectured, in '65,
that there is no polynomial time algorithm for it.
Now I've, obviously what you really want is, the answer.
You either want a proof of Edmund's conjecture, that there's no efficient
algorithm for TSB, or, even more astonishingly, you'd want a polynomial
time algorithm that solves the problem. But we also have to face the reality that
we may not know the answer for sure to this question, for quite a while.
Years, certainly. Decades, probably.
Centuries, who knows, maybe. So the challenge then for people thinking
about algorithms and computation, is to nevertheless devise a theory which
usefully differentiates tractable problems from relatively intractable
ones, even in the face of this massive
deficiency of our understanding of what is possible and what is impossible.
And the brilliant way out is relative difficult as now personified by
NP-completeness. If you want to amass extremely strong
evidence of the computational intractability of a problem, prove that
it's MP complete. Prove that a polynomial time algorithm
for the problem, if it existed, would solve thousands upon thousands of
unsolved computational problems.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
