P and NP

Loading...

Del curso dictado por University of California San Diego

Advanced Algorithms and Complexity

291 calificaciones

University of California San Diego

Advanced Algorithms and Complexity

291 calificaciones

Curso 5 de 6 en SpecializationData Structures and Algorithms

You've learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We will start with networks flows which are used in more typical applications such as optimal matchings, finding disjoint paths and flight scheduling as well as more surprising ones like image segmentation in computer vision. We then proceed to linear programming with applications in optimizing budget allocation, portfolio optimization, finding the cheapest diet satisfying all requirements and many others. Next we discuss inherently hard problems for which no exact good solutions are known (and not likely to be found) and how to solve them in practice. We finish with a soft introduction to streaming algorithms that are heavily used in Big Data processing. Such algorithms are usually designed to be able to process huge datasets without being able even to store a dataset.

De la lección

NP-complete Problems

Although many of the algorithms you've learned so far are applied in practice a lot, it turns out that the world is dominated by real-world problems without a known provably efficient algorithm. Many of these problems can be reduced to one of the classical problems called NP-complete problems which either cannot be solved by a polynomial algorithm or solving any one of them would win you a million dollars (see Millenium Prize Problems) and eternal worldwide fame for solving the main problem of computer science called P vs NP. It's good to know this before trying to solve a problem before the tomorrow's deadline :) Although these problems are very unlikely to be solvable efficiently in the nearest future, people always come up with various workarounds. In this module you will study the classical NP-complete problems and the reductions between them. You will also practice solving large instances of some of these problems despite their hardness using very efficient specialized software based on tons of research in the area of NP-complete problems.

Brute Force Search5:42

Search Problems9:44

Traveling Salesman Problem7:57

Hamiltonian Cycle Problem8:09

Longest Path Problem1:42

Integer Linear Programming Problem3:08

Independent Set Problem3:07

Conoce a los instructores

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Now when have a formal definition of the search problem and

when we've seen a few example of search problems, we are ready to state

the most important open problem in computer science.

The problem about classes P and NP.

So recall once again that the search problem is defined by an algorithm C

that takes an instance I and a candidate solution S, and

checks in time polynomial in I where the S is indeed a solution for I.

In other words, we say that S is a solution for I if and

only if the corresponding algorithm C of I and S returns to,

then the class NP is defined just as the class of all search problems.

The name of this class stands for non-deterministic polynomial time.

This essentially means that we can guess a solution and

then check its correctness in polynomial time.

That is a solution for a search problem can be verified in polynomial time.

The Class P on the other hand,

contains all search problems that can be solved in polynomial time.

That is all such problems for which we can find a solution in polynomial time.

So to summarize, once again the class P contains all search problems

whose solution can be found efficiently.

This class contains in particulars, as minimum spending 3 problems.

The shortest path problem, the linear programming problem,

the independent set on trees problem.

The class NP contains all the problems whose solution can be verified efficiently

that is given an instantiation solution for this instance solution,

we can check in polynomial time.

In the size of this instance, whether this is indeed a solution for.

This class contains such problems as a problem,

the longest path problem, problem and independent set on general graphs.

The main open problem in computer science asks whether these

two clauses are equal, namely whether the clause P is equal to the clause NP.

This is also known as the P versus NP question.

The problem is open, namely we do not know whether these two clauses are equal and

this problem turns out to be very difficult.

This is a so-called Millenium Prize Problem.

There is a $1 million prize from Clay Mathematics Institute for

resolving this problem.

Note that if P is equal to NP, then all search problems,

I mean all the problems for which we can efficiently verify a solution,

they can be solved in polynomial time.

In other words, for all the problems for which we can

efficiently verify a solution, we can also efficiently find a solution.

On that hand, if P is not equal to NP, then there are search problems for

which there are no efficient algorithms.

So there are problems like, for example, problem for

which we can quickly check whether a given candidate solution is indeed a solution,

but there is no polynomial time algorithm for finding such a solution efficiently.

At this point, we do not know whether P is equals to NP or not, I mean,

where they are such problems for which there are no polynomial time algorithms.

In the next part, at the same time we will show that all the problems that we

mentioned in this lecture namely the problem, the longest path problem,

the traveling salesman problem, the inter linear programming problem

are in some sense, the most difficult search problems in the class NP.

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.

Descargar en la App Store

Consíguelo en Google Play