0:00

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.

8:39

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.