Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

University of California, San Diego

NP-Complete Problems

University of California, San Diego via edX

Overview

Step into the area of more complex problems and learn advanced algorithms to help solve them.

This course, part of the Algorithms and Data Structures MicroMasters program, discusses inherently hard problems that you will come across in the real-world that do not have a known provably efficient algorithm, known as NP-Complete problems.

You will practice solving large instances of some of these problems despite their hardness using very efficient specialized software and algorithmic techniques including:

  • SAT-solvers
  • Approximate algorithms
  • Special cases of NP-hard problems
  • Heuristic algorithms

Syllabus

Week 1: 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.

Week 2: Coping with NP-completeness: special cases
After the previous module you might be sad: you've just went through 5 courses in Algorithms only to learn that they are not suitable for most real-world problems. However, don't give up yet! People are creative, and they need to solve these problems anyway, so in practice there are often ways to cope with an NP-complete problem at hand. We show that some special cases on NP-complete problems can, in fact, be solved in polynomial time.

Week 3: Coping with NP-completeness: exact and approximate algorithms
We consider exact algorithms that find a solution much faster than the brute force algorithm. We conclude with approximation algorithms that work in polynomial time and find a solution that is close to being optimal.

Taught by

Daniel Kane and Alexander S. Kulikov

Reviews

Start your review of NP-Complete Problems

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.