What's going on here?

One second, open up.

Oh, what?

One second.

Okay, now it's opening up.

Wow.

Okay.

What's going on here?

There we go.

Okay, let's now share it.

But the Microsoft updated itself.

And so I was stuck.

All right.

Where is it?

Here we are.

Okay, good.

We're still connected.

Good.

Very good.

Share your screen.

Where are the notes?

Here it is.

Yay.

Okay, so now.

Okay, thank you all.

Let me... one second.

One more.

Good.

All right.

So what's on the screen is a page from...
what's his name?

From Karp's paper.

Page 96, if I'm not mistaken.

And I include it in the notes.

What I did, what I added to it is that
Karp has numbering.

And it's not so obvious how he does his
numbering.

In some sense, it's a... it's a... well,
it's a little hard to explain.

But anyway, it's a little bit like a
breathless search, but it's not really.

But anyway, however he does
the numbering, you sort of see

half of them is on one side,
half of them on the other side.

It's not like a traditional order of
traversal of trees.

Anyway, so I personally numbered them for
you.

So the numbers I added, that's not in the
original paper.

So that's going to be a... what you call
it?

A tab in the notes that I sent you last
night.

I already sent... in case
anyone's curious, I already

sent you the notes last night,
which has many, many tabs.

We're not covering all those tabs today.

In fact, the... the... this set
of notes that I emailed you will

cover probably the next two
weeks of note... of discussions.

What I will do instead
is I... when I email you

later, I will tell you up to
what point did we cover.

So that way you could... in terms of the
MCQ and in terms of the electric keywords,

you'll know what's included.

Okay?

Anyway, but we will
constantly make a reference

for the next... for a
while to this chart.

Again, I added the numbers.

The numbering... the numbering comes from
CAR.

But the actual numbers in the chart,
I added.

Anyway, just to remind you.

So if we could take a little look here on
number 12 and 13.

Chromatic number and click cover.

And now let's... back to the notes here.

And just to remind you what a reduction
is, and then we'll go through the problems.

All right.

So now, the first problem was satisfiability,
which is the root of this tree on top.

Number one.

And that was not... although we call it
CARP 21, the tab is called CARP 21.

And there are 21 numbers here.

CARP did not actually prove number one.

Cook did.

And Cook showed that all NPR problems must
reduce to satisfiability.

And we will go through that proof at the
end of the semester.

It will not take weeks.

It will take one session and we'll go
through this proof.

But anyway.

Now, Cook, therefore, only needed in his
definition of reduction one direction.

Because that's all he was going to prove.

So his definition of reduction is every
NPR problem to satisfiability.

All right.

That CARP wanted to show other problems,
other equivalent hardness.

NP-hard in the other direction.

But he didn't hold that reduction is one
direction.

He held reduction was two directional.

But in terms of NP-hard, he never had to
prove one of the two directions because he

relied on Cook, who showed the other
direction in essence.

Anyway, so that's the situation.

And then we mentioned that 11 had a third
definition of reduction, which dealt with

the complexity of finding the missing
piece of information, either call it a

certificate, witness, other names as well,
in terms of the missing piece of

information you need in order to solve
your problem.

All right.

Now, just in terms of 12 and 13,
so let's use that example.

So for example, chromatic
number is number 12 here on

the right, and then to its
right child is click-cover.

So what would be the terminology?

At that point of the tree where chromatic
number connects to click-cover,

chromatic number is
already known to be hard at

this point, whereas
click-cover is not yet known.

Okay?

So it's hard.

It is known to be NP-hard at that point,
but its child click-cover is not yet known.

All right.

Click-cover in terms of our
terminology, whether A reduces

to B, click-cover is the
A, and what you call the B.

Well, yes, this is a little bit odd.

Okay.

All right.

Ignore that.

Ignore the notation for a second.

Anyway, so click-cover is A, and chromatic
number is B, and B reduces to A.

Here, less than or equal means reduces to.

B reduces to A.

It's a little bit of a counterintuitive
convention, but that's the way it's done.

That's the way it's said.

Okay.

And chromatic number is the parent.

Click-cover is the child.

The root of the tree is SAT.

SAT is Satisfiability.

We'll define that formally in a second.

We've defined it before, but just so that
we could get a complete discussion of all

the problems, I'll define it one more
time.

And when we start the COP21 problem, the
definition is the third tab of the notes.

Now, what does it mean to reduce?

It's that the click-cover, so we don't
know that yet click-cover is hard.

We know that a chromatic number at this
point is MP-hard.

Click-cover solves chromatic number.

The child solves the parent's problem.

And then we say that chromatic number
reduces to click-cover.

We also could say click-cover reduces from
chromatic number.

Conclusion, click-cover is as hard as
chromatic number.

Okay?

So, here are the abstract ways of saying
it.

And the reduction tree summary is the next
tab.

And, okay, just so you know it's the next
tab.

It's there.

But anyway.

And COP1 is the root of the tree.

Fine.

Anyway, that's just the terminology.

So, we're now going to embark on the 21
problems.

Now, the way I'm going to present the 21
problems is that I'm going to...

Because the way it appears in COP3,
except for some few cases, there is no...

You don't get an obvious
extension, obvious relationship,

as to why a problem is
where it is on the tree.

Some yes, but mostly no.

So, in order to make life a little more
simpler for us, I'm going to organize the

problems into different groups based on
the data structures involved, based on the

exhaustive search proof
force manner of solving

them, et cetera, based
on the way to verify them.

Whatever grouping I could find in order to
perhaps relate problems to each other.

Okay?

So, let's get started.

The first group of problems are problems
1, 2, 11, and 18.

Problem 1 is Satisfiability.

Zero on integer programming.

Satisfi... On Satisfiability.

SAT's right is Satisfiability with at most
three literals per clause.

So, those three are actually near each
other.

But then 18 is all the
way on the right on

the bottom knapsack in
the middle of nowhere.

Anyway, so what does all of these problems
have in common?

They all involve bit string storage of the
solutions, which would mean that if you

did an exhaustive search, a proof force
search, you would have to generate all bit

strings and then plug it in and see which
one is the solution.

Satisfiability.

Now, what does Satisfiability mean?

Given a Boolean predicate,
a function, a total function,

whose output is only zeros
and ones, true and false.

Well, we say false and true.

Zero is false and one is true.

That's the convention used.

Given a Boolean predicate, P, of x1
through xn, the variables of x1 through

xn, find an instance, the values of the
variables x1 through xn, such that the

Boolean predicate's output is true,
one, based on those inputs.

Okay.

Now, I kept the next line separate for the
following reasons, because in discrete

math, you have the line
four definition, but they do

not necessarily, not all
authors impose line five.

Karp and Cook did.

It's not...

I don't know if it's an argument per se,
but anyway, that's just the way they did it.

So, number five says that not only must the
output be true, the inputs must be true.

So, xi, the variables must also have
inputs, zeros and ones.

Okay.

The variable inputs and the output must be
Boolean.

All right.

But in discrete math, usually a lot of the
authors only say the output is Boolean.

The inputs could be numbers and the
Boolean predicate relates those numbers

and tells you whether the relationship is
true or false.

Anyway, the solution
could be stored in a bit

string array of zeros
and ones of length n.

If you have n, according to Karp,
if the n variables are all zeros and ones,

so then all you need is a listing,
a sequence of n zeros and ones,

corresponding to the variables x1 through
xn.

Okay?

So, that is satisfiability
and it could be

stored and generated if
you want to prove for us.

If you didn't have a
non-deterministic computer, you only

had a deterministic computer,
you could try them all.

It'll take a while.

Exponential.

All right.

So, that's satisfiability.

Since we're talking about
satisfiability, I'm going to

jump to number 11 because
it's also called satisfiability.

But here it's with at most three literals.

Three literals means three variables per
clause.

So, we'll get back to number two in a
second, Karp 2, but let's do Karp 11

because it's similar to...
It's a spin-off of Karp 1.

So, it's identical in concept and in
structure as its parent satisfiability.

This is sometimes called SAT-3.

Satisfiability sometimes is called SAT,
although some people call it SAT, S-A-T-Y.

But anyway, this one's called SAT-3.

So, the difference is a formatting
constraint on the appearance of the user's

Boolean predicate P. Whereas, in
Satisfiability, there was no restriction

on the ands, ors, and nots and how it
appears.

In SAT-3, there is a restriction of
format, which is the predicate P must be a

conjunction ands of clauses, meaning
groups of parentheses.

Parentheses is a clause.

Okay?

And between the clauses are ands.

And within the clauses are ors.

So, ands outside the parentheses and ors
inside the parentheses.

Now, what's in the parentheses?

Variables.

Variables.

And they're ored together inside the
parentheses.

But, each parentheses, each clause,
cannot have more than three variables.

Possibly duplicates.

You don't generally want to do that,
but possibly so.

But it can't have more than three
variables.

That's why it's Sat-3.

Okay?

And, but with the...
That's in terms of the ors.

There is no constraint on negation,
except that it's limited to variables.

You can't negate a clause of variables,
but only variables can be negated.

The reason for that, which I
didn't want... I'll say it out loud.

Well, okay.

Let's, let's add to that.

All right.

The reason for that is the following.

One second.

You would have to remember your discrete
math.

Clauses can't be, cannot be negated.

Because according to
DeMorgan's laws, which you should

know, and look it up if you
don't, from discrete math.

Ouch.

By negating the clause, you will have
transformed the ors of the variables into ands.

Okay.

So if you look into DeMorgan's laws,
the, it's not just the, if you,

if you negate the clause,
you, what you will have

done is actually
transformed the ors into ands.

So look at DeMorgan's laws in discrete
math and you'll be able to understand that.

Anyway.

Now, the reason this is viewed as
formatting and not a complete revision is

that CARP showed, in other words,
how do you, you know, once you say you

restrict how the Boolean predicate can be
written, how do you know that you can,

you can write any Boolean predicate in
this format?

Maybe by restricting it, you've changed
the problem radically.

Right?

So the, the reason this is viewed as
formatting and not a complete revision or

variant is that CARP
shows that any arbitrary

Boolean predicate can be
written also in this format.

As such, this format can be considered a
normal form.

A normal form is a
standardized format which is

equivalent to the original
provided general structure.

Here also, the variables must be Boolean.

The solution will be stored in a bit
string of length n.

Now, one of the other parts of,
of CARP's paper on pages 89 and 90 is that

if you start playing around with some of
the definitions, all of a sudden something

that was MPHARD is no
longer HARD and is in the, is in

actually P. So on line 28, over
here I write that note, SAT2.

What's SAT2?

SAT2.

So it's similar to SAT3,
but only allows one

or two variables to
appear in each clause.

Okay?

So that is the case that you
limit the parentheses to only

have two, only to have two
variables and not three variables.

Alright?

Just so I just have a, I just want to make
sure the sound, can I do a sound check?

If you could just text if the sound's
okay.

I just like to do that just to make sure
we're doing okay.

We're doing, thank you, Lauren.

Okay, great.

Fine.

We're done.

Thank you very much.

Let's continue.

Good.

Alright.

So SAT2 is in P, where
you limit the number of

variables in each parentheses
to only two variables.

Anyway, it's identical.

SAT3 is identical in some sense to
satisfiability in that you have N

variables and that all the values are
zeros and ones.

So you could generate
similarly a solution by

just simply having a
bit string of length N.

Okay?

So it's a very similar problem.

Now, CARP2, which is a child of
satisfiability in the center here,

CARP2, so the child on the right,
the child in the middle, both have a

similarity in that bit strings are the
data structure used to store the solution.

Click on the left, which is also a child,
does not.

So just because they're
all in the same level,

they don't all have anything
to do with each other.

So 0, 1 integer programming.

So that's number 2, CARP number 2.

So CARP number 2, 0, 1 integer
programming.

So programming means... You
know, I think this would be better served.

The number here may not be as good.

Let me put it in the center, because
otherwise we won't be able to...

Anyway, whatever.

The 2 is too close to the 0.

Anyway, 0, 1 integer programming.

Programming means solving a system of
equations.

Okay?

So we think we were programming first.

Mathematicians were programming.

For example, they have linear programming,
not nonlinear programming.

That doesn't mean code.

It means solving a system of equations.

So the last word programming means solving
a system of equations.

Why do we call it integer programming?

Because the numbers
involved are all integers, meaning

there are no real numbers
involved in the set of equations.

Why do we call it 0, 1 integer?

Because we further constrain x1 through xn
to be a boolean, 0, 1.

Integers more is also not just on the
variables, constrains all coefficients.

Any number, as far as I know, I believe
so, all coefficients to be integers.

Anyway, 0, 1, 0, 1 integer programming
further constrains x1 through xn to be 0, 1.

The system of equations has m equations
with n unknowns, x1 through xn.

But the point is x1 through xn are
boolean, only zeros and ones.

And an addition has a target vector of
values b, which is a vector of length m.

So in matrix multiplication, you would say
that matrix A times the single array,

the vector, one-dimensional array x,
equals a one-dimensional array b.

And a and b are given by the user.

And the programming system is supposed to
determine the... solve for x.

Determine the x vector of zeros and ones,
the boolean values.

So therefore, the
solution will be stored in

a bit string of zeros
and ones of length n.

Right?

Because that's all you need.

The a, all the coefficients are given.

The b, the other
coefficients, on the other

side of the equality is
given of the equation.

What's missing is knowing what the x1
through xn are equal to.

You could store that solution in also a
bit string of zeros and ones of length n.

Now, here's another note about NP.

Now, CARP gives a different one.

CARP on page 8990 mysteriously says
solving equations without constraints.

In our standard linear
algebra, standard solving

for x that you've done in
trigonometry or algebra.

So, you know, just solving equations where
there are no other constraints is in P.

But I give one that I think is a little
closer, which is that solvability of

general linear equations, meaning linear
programming.

And that could actually have certain
constraints.

Anyway, linear programming
is more advanced than that,

but it's much closer, in
fact, to integer programming.

Solving of linear programming
is in P. The P version

has no restrictions to the
values used or obtained.

They only have to be zeros and ones.

In modern times, linear programming has
shown to be in P. It was not known.

It was assumed because...

What's his name?

What's his name?

The simplex method...
What's his name?

I forgot.

All right.

It's escaping me.

But the simplex method was assumed to
be...

Everyone knew that the simplex method,
which solved linear programming,

or what they used to try to solve linear
programming, was... It worked very quickly.

They just didn't know why.

And then somebody...

Kachian and then Karmakar, with different
proofs, showed that, in fact, it's in P,

which is why everyone understood.

That's why it's so fast.

Danzig.

Danzig showed that...

They created the solution
called simplex algorithm,

simplex method, to
solve linear programming.

But no one knew that it worked so quickly.

The reason it works quickly is because
it's in P. All right.

That's 01 integer programming.

And now we have knapsack.

And it's like the name implies.

Meaning... Consider packing a
suitcase for international travel.

The reason you'll see why I phrase it that
way.

That's not Karp.

I'm giving you a more practical
interpretation.

And not just sticking to the official
mathematical definition that Karp gives.

It's the same in the
end, but I think it gives a

little more application and
you understand it better.

Consider packing a suitcase for
international travel, where there are

strict rules on the total weight of the
suitcase.

It is beneficial to the user
to pack as many items as

possible, which translates
to finding a perfect packing.

Meaning if you're traveling far,
so it's helpful to you to have extra

clothing, extra books, maybe extra food,
maybe whatever is convenient for you.

It makes travel easier.

So you might as well, you're paying for
it.

You might as well pack
as much as you can into the

suitcase as long as you
don't go over the weight limit.

Okay?

That's the general idea.

So it's in your interest to pack fully.

If they say 50 pounds, then fill up 50
pounds total in the suitcase.

If they say 70 or 72
pounds, whatever the

case was, then it's in
your interest to do so.

Okay?

It helps you to have another sweater
there, another book there, another

whatever, device or
food, the can of food there

with you, whatever
you're doing on your travel.

Now mathematically, the
user on line 33, mathematically

the user has N possible
elements to pack.

In other words, you don't know yet what's
going to fit in your suitcase.

So you're going to put
out, spread it out on your

mattress, all the items
that you could possibly pack.

And then you're going to make sure in this
mathematical approach, you're going to

weigh each item, because
you need to know in

the end how much
weight is in the suitcase.

So each item has a weight A sub i.

I'm using the letters that CARP uses.

You could read the shorthand in CARP's
paper.

A sub i are the weights.

And the maximum total weight for the
packing is a constant B.

Whether it be 50 pounds, 70 pounds,
whatever it is.

Now, there are N possible elements to
pack.

Not all of them are you going to take.

So now you have Boolean variables
associated to whether you take them or not.

If you take them,
so then the variable

corresponding to that
item will be true or one.

If you don't take that item, you don't
pack that item, then the variable or

weight, the variable will be false,
and the weight will be zero.

Not the weight, the value of the variable
will be zero.

So you have items with weights a sub i,
a1 through an, and then you have variables

x1 through xn telling you whether or not
to take them, all right?

And whether or not you're going to pack
them.

And the goal is that if
you add up a sub i times x

sub i, so when the x sub
i is 0, you didn't take it.

If you didn't take it, the weight doesn't
count.

If you did, x sub i is 1,
then you took the item and

the weight counts in the
total weight of your suitcase.

And the goal is to get a perfect packing
to equal b.

So these items can be stored in a bit
string, an array of zeros and ones of

length n, where each zero
and one will tell you whether

or not you are going to
take item x sub i or not.

Now, a variation... well,
actually there are a zillion

variations in practice in
the literature for knapsack.

But a variation that's known to be in P,
Karp doesn't mention this, but a variation

that's known to be in P is called
fractional knapsack.

Fractional knapsack is
where you could... let's

say one of your items
was a loaf of bread.

And the loaf of bread makes you go over
the B limit, the 50 or 70 pounds,

by five ounces.

So with the loaf of bread,
you could take a cutting

instrument and cut off the
piece, the five ounces of bread.

And then you could take the bread,
but you won't have the whole loaf of

bread, you'll have some of it,
right?

So that's fractional knapsack,
where you have the luxury to take the

item, but you're told you can't take the
whole item, it's too much.

So take only part of it.

If that were the case, then you
could actually solve knapsack in P.

In polynomial amount of
time, there actually is, I believe,

a variation of a greedy
algorithm that could do it.

A common example is a spice salesperson,
right?

So you have spices and they weigh.

And if it's too much weight, so you could,
let's say you're taking, you're going to a

show, to show, to, you
know, a business show, and

you're trying to display
all the spices you sell.

And you're flying,
and you're taking these

spices with you in
your plastic or glass jars.

And I guess if you're flying, maybe it
would be plastic, a little safer.

Anyway, in your luggage that goes below.

Anyway, so the point is that if it turns
out that it's a slightly over,

you could spill off some of the spice.

And then make the perfect packing.

Just anecdotally, something like this
knapsack situation actually happened to me.

I was flying, at that time,
it's irrelevant which airline,

but I was flying out of
Newark, wherever I was going.

I don't remember.

I won't say which airline.

Anyway, and I literally was two ounces
over the limit.

Something like that.

I was ounces over the limit.

So the person behind the counter who gives
the stickers and the tickets said,

well, sir, you're going to have to remove
an item, you know, four ounces,

whatever it was.

Literally, it wasn't even a pound.

Some ounces are out of the suitcase.

I said, well, you know, what do you
recommend?

So the person says, take out one shoe.

So I had to unpack and pull out a shoe,
one shoe.

The other shoe was within the weight
limit.

But the second shoe, the person said,
carried me over the limit.

So everyone's waiting behind me,
not understanding why I'm unpacking and

repacking, wasting everyone's time while
this person made me take out a shoe.

Then, so I said to
the person, well, what

do you think I'm going
to do with this shoe?

So I took the shoe and I put it in my
pocket.

I was wearing a coat, I think it was the
winter.

So I put it in one of my coat pockets,
the shoe.

So after doing that, the person said, fine,
and allowed my suitcase to go through.

And I made a comment as follows.

I said, I'll do what the requirements are.

But please do realize that in terms of the
plane, it's the same weight.

Because this shoe is now in my coat pocket
and it's still going on the plane.

So, you know, what was gained here and the
fact that I was a few ounces over the

weight limit and everybody wasted their
time waiting because they had to go

search, take the clothing out, find
one shoe, take it out and then repack.

It was the most ridiculous thing.

Anyway, that actually happened.

And the point is that this
problem could also, knapsack

could also be solved in a
exhaustive search manner.

The solution is basically
a string of zeros and ones,

an array, a single dimensional
array of zeros and ones.

Where the ith item corresponds to the...

Whether you take the ith weight,
the ith item to pack.

If it's zero, if the ith bit is zero,
you did not.

If the ith bit is one, you did.

So, all of these four all have
in common that their solutions

could be stored in a bit string
of zeros and ones of length n.

Alright, so that's problem one,
two, eleven, and eighteen.

Okay, the next group of problems are
seven, eight, nine, and ten.

Now, these in the CARP 21 actually are
near each other.

Seven, eight, and nine are all children of
node cover.

But ten is a child of nine.

Alright.

Now, there's some interesting things about
this.

Anyway, let me first tell you the
commonality.

Sorry, I'm a little tired.

The commonality is that seven, eight, nine,
and ten all involve cycles in some manner.

Okay, they involve some aspect of cycles.

A cycle, to remind you from
discrete mathematics, is a

pathway in a graph that starts
and finishes at the same place.

So you start at node six, you go to seven,
eight, twenty-three, two, and back to six.

Okay?

And there's no repetitions.

And there must be an edge that exists for
every other...

You know, it's between any two nodes,
an edge must exist.

And then finally, an edge back to the
origin where you started.

That's the definition of a cycle.

Now, in the case of feedback...

Okay, let's talk about nine and ten, because
it's a little bit easier to understand.

Not that seven and eight's hard, but there's
an interesting twist in seven and eight.

So in problems nine and ten, directed and
undirected on the left of this tree,

directed and undirected deals with the
edges that are found in your graph.

If the edges are one-directional,
that's called directed.

If the edges don't allow you to
have a two-way communication,

you're allowed to go in both
directions, that's undirected.

The word circuit is an old-fashioned
English word for our modern word cycle.

The word circuit is the Hamiltonian
circuit.

Hamilton or Hamiltonian circuit is an old
problem.

So in old English, the word circuit means
cycle.

Okay, so directed and undirected is the
nature of the graph.

Whether the edges only have specification
in one direction or the edges allow you

to... It's a two-way street, you're
allowed to go in both directions.

Directed means one direction,
that all the edges in your

graph only specify you're
allowed to go in one direction.

Whereas undirected says
that the edges in your graph

allow you to go between
the vertices in either direction.

A circuit means we're trying to find a
cycle.

Does a cycle exist amongst the vertices of
your graph?

What is Hamilton, or Hamiltonian as it's
sometimes called, what does that mean?

That every note in your graph is involved.

It may not be too... well,
it's not so simple either,

but identifying a cycle
locally may not be too bad.

But here, the question is, if you have
every note of your graph involved,

can you list the vertices in a manner that
there's no repetition?

Every vertex is used, and
there's an edge from one vertex

to the next, and that last
vertex goes back to the first.

If so, that's called a Hamiltonian
circuit, a Hamiltonian cycle.

A circuit, again, is a cycle.

In loose terminology, we would say a loop,
but in graph terminology, you can't.

A loop is an edge that goes from the
vertex immediately to itself.

So the word loop is generally avoided.

But anyway, circuit and cycle is generally
the same term.

Alright, so that's problems 9 and 10.

I'm sorry, 9 and 10.

Alright, now, how would you try to...

Let's say you don't have a
non-deterministic machine.

In other words, what would a
non-deterministic machine do?

A non-deterministic machine would say yes,
there is a Hamiltonian...

More than that.

It wouldn't just say yes.

The Hamiltonian...

It could say that.

But the Hamiltonian...

The non-deterministic machine would list
you, if you asked it to, would actually

list the sequence of the cycle involving
all the nodes.

And you could verify that it's a cycle
very easily.

First of all, are all the nodes listed?

And number two, is there an edge from each
node to the next?

And then the last node back to the first?

But basically what you're...

Now, let's say you did not have a
non-deterministic machine.

Let's say you had a deterministic machine.

So what you would have to do is generate
all the permutations of all the nodes.

Because what you're looking for is a
sequence.

A sequence of all these nodes.

And then you'll verify whether there is an
edge from each node to the next.

And we know...

In fact, we showed it when we discussed
exhaustive searches a week or two ago,

that n factorial is greater or equal to 2
to the n.

It's even worse than exponential.

All right.

So those are the cycles
involved in directed

Hamiltonian circuit
and undirected circuit.

Okay.

So circuit and cycle is the same.

Let me say loop...

Let me put that separate.

Loop can also...
Loop also, but...

is restricted to one edge of a node to
itself.

Okay.

So it's a rather restrictive definition of
loop.

But circuit and cycle mean cycles.

Well, obviously it does.

Okay.

All right.

What is feedback?

Feedback node and feedback arc set.

So you're looking for feedback.

And if you know any
general terminology in

electrical engineering,
they say a feedback loop.

What we mean here is a cycle.

So basically the word feedback is hinting
at cycle.

Anyway, a node set
is obviously looking for

vertices, and an arc
set is looking for edges.

So what's the situation?

Given a graph and a
bound k on the sides of the

feed set, of the feedback
set you're looking for.

So the user... The problem
allows for a parameter k.

Now, we'll do this in a second.

I just want to remind you.

On the bottom, I mentioned this point about
the... And we've mentioned this before.

On line 58 here on tab number one in the
notes.

CARP adds an extra parameter.

Because when...

Again, as I described
this, we've mentioned

this before, so I won't
repeat all the details.

You've... This is...
This little last blurb here.

What's on the screen now has been included
in previous notes as well.

But the point is that optimization
problems are hard to verify.

If I say to you, trust me, this number
will get you the best possible output.

The maximum value.

And you plug it in and it gets you a very
good value and you're happy.

But how many notes the best?

How do you know you've optimized?

You can't prove that.

Not so easily.

Unless you try every possible number.

And then, yeah, it's the best.

But if you're trying every possible
number, you didn't need non-determinism.

That's an exhaustive search.

It took exponential amount of time.

So, CARP transformed optimization problems
into decision problems.

Not saying the max, but rather,
can you find the max with only within K?

Where, you know, your max
is less than or equal or greater

or equal to K depending
on whatever the situation is.

So, by adding K, it becomes not just... it
transforms into a decision problem.

Can you find a max that matches or is
within the tolerance K?

So, it may not be the true max,
the global max, but it is a max.

So, here also, there's a bound K on the
size of the feedback set.

Now, here's an irony.

What does it mean to be
a feedback... Well, okay.

The irony in a second.

You'll see.

But, what does it mean to be a feedback
set or a node set or arc set?

Again, the node set looks for vertices and
the arc set looks for edges.

If you have a graph,
ignoring Hamiltonian, as

I mentioned before,
there are cycles locally.

Right?

These five... you have a hundred vertices.

These five may be a cycle.

It's not Hamiltonian unless all a hundred
is part of a cycle.

Now, let's imagine... ignore how we're
going to figure this out for a second.

But, let's imagine the set of all cycles
in your graph.

Okay?

Ignore how you could generate this.

But, let's imagine that you have... you
know where every cycle is in your graph.

Now, two different cycles could overlap.

Two different cycles will share some
vertices.

Two different cycles... different cycles
will share some edges.

Within... within any one cycle, no
vertex or edge... well, no edges shared.

But, within different cycles, there could
be an overlap.

So, if you knew that,
what does it mean to be a

feedback cycle node set
or a cycle arc set with K?

Okay?

Can you find K edges such that every cycle...
let's take arcs... let's take... okay.

Since I already said arc, let's do problem
eight, which is a feedback arc set.

Arc means edge.

All right?

Since I already said edges.

Let's... let's take the theoretical set of
all cycles that exist in your graph.

You have a thousand nodes, a graph,
and there is many cycles.

Imagine you could identify all those
cycles.

And the question is... and then you have a
parameter K.

K is, let's say, 10.

And I want you to choose, in the case of
problem eight, feedback arc set,

I want you to choose 10 edges.

In the case of feedback node set, I
want you to choose 10 nodes, 10 vertices.

Such that every cycle has something in
common with your feedback set.

So if it's an edge set, then every...
every cycle must have at least...

at least one edge in common with
somebody in your feedback arc or edge set.

If we're dealing with feedback node set,
then every cycle must have at least one

vertex in common with
some... some node that

you chose in your
feedback vertex or node set.

It must have something in common.

Okay, where's the irony?

The irony is the following.

There is no easy way to generate all
cycles in a graph.

There is no... you're not going to find it
in any book.

You could do a crazy exhaustive search to
find those cycles.

But if you did that, so then solving the
problem, once you've spent the exponential

amount of time identifying
every cycle, then the

feedback node set and
arc set is a simpler problem.

But the point is that there
is no known algorithm

to generate... easy
algorithm to generate cycles.

So the set of cycles itself is a
theoretical construct.

It's not a practical one.

Not logistically.

You could do it.

It's not impossible.

It's not unsolvable.

It's solvable.

But it's very... it's not efficient.

You would have to do... try every
possibility and bump into the cycles.

It's an exhaustive search.

So... so the problem is, how do you verify
the definition?

Because remember... remember, although I
didn't stress that point on the definition

reduction, I did in a
previous point, which

is the small letter P
that some people have.

Oh, here it is.

To emphasize the need... on line 39 here.

To emphasize the need to transform between
the NP problems within a reasonable amount

of time, many put a P at the foot of the
less than or equal.

Okay?

Many put a P at the foot of the less than
or equal to emphasize the fact that...

to transform, to reduce
from one of the problems to

the other, can be done
in a short amount of time.

The verification can be done in a short
amount of time.

All right?

So that's a key issue.

How do you verify?

Let's say I figured out the 10 edges,
and I guarantee you that every cycle in

your graph has something in common,
at least one edge, maybe more,

something in common with my 10 edges,
which I call a feedback arc set,

or 10 nodes in case I have a feedback node
set.

Now, how are you going to verify that?

You don't even know what the cycles are.

So how are you going to
verify that every cycle has

something in common with
this supposed feedback set?

So CARP was genius here, every step of the
way.

The paper is unbelievable.

CARP realized the following.

You don't have to.

In order to verify...

Let me repeat this.

You do have to verify, but you don't have
to do what you think you have to do.

In order to verify, let's again,
then the non-deterministic machine

guesses, and supposedly correctly guesses,
K edges, 10 edges, and guarantees you that

every cycle in your graph goes through at
least one of those edges, maybe more,

but has something in common.

Now you're going to verify that.

Now you're going to verify that.

So although the definition is about
cycles, you don't need, believe it or not,

mathematically, to generate a single cycle
in order to verify that.

Why?

Because if it's true, for
example, feedback arc set,

because I think it's a
little easier to connect to.

If it's true, feedback arc set,
that every cycle goes through somebody in

your, or one or more edges in your
feedback arc set, then if you were to

delete those K edges from your graph,
then no cycle could remain.

You've broken every cycle.

If every cycle has some edge in common,
not the same edge, but some one or more

edges in common with your feedback set,
then by deleting your feedback set,

you have broken every cycle.

Now how does that help you?

Because although it's really
expensive to generate all

cycles, it's polynomial
to test if it has no cycles.

And there are many, many algorithms.

Here on line 51, there are many
algorithms.

Transitive closure, transitive closure,
matrix multiplication, topological sort,

depth of research, backtracking.

There are many algorithms for testing if
there's no cycle.

To generate all cycles, that's crazy.

But there are well known polynomial
algorithms to

test if there is no cycle.

So by deleting your arcs,
your feedback set, then

the remaining graph can
no longer have a cycle.

Use one of the many published polynomial
algorithms for testing this.

And you'll be able to verify whether your
feedback set is a correct feedback set.

So that's a fascinating irony twist here.

That although the definition
involves cycle on 7 and 8,

you don't need to generate
a single cycle to test it.

Anyway, problems 7, 8, 9, and 10 all
involve cycles.

And at least here, they seem to be near
each other in the tree.

Okay, now, one little separate
problem is that problems

3 and 13, it's not a problem,
just to make you aware.

Problems 3 and 13 have the word click or
clique.

It's a spin-off of a French word.

Anyway, click or clique, 3 on the top left
and 13 on the far right.

Click and click cover.

Now, what's a click?

A click is a subset of
vertices such that every

vertex is connected
to every other vertex.

So you can look up the definition,
the point here, and later we'll talk more

about it, because when we get to 3 and 13,
we'll spend more time.

The reason I make this
note over here is that if you

have a click, then you
also have a cycle within it.

A click, a click is more than a cycle.

But if you have a click, then you also
found a cycle.

So the question I just mentioned is why
didn't I include it here?

So the answer is because the focus is not
on cycles.

Click is not a cycle.

The click problems are not about cycles.

The click problems are about clicks,
which involve much more.

It turns out that technically, if you
have a click, you also have a cycle.

But I don't include it
here because these

problems all in their
definitions involve cycles.

Whereas 3 and 13, the next problems are
about clicks.

Okay?

All right.

The next problems in our group...

I just want consistency.

I don't use the word CARP above.

Either way is fine.

All right.

Click and click cover.

And then we have some interesting ones.

Okay.

We'll wipe out those in a minute.

Okay.

Oh, yeah.

This is a fun set.

Hold on.

I just want to for our
notes here to be a

little consistent in terms
of the notation here.

It won't change the notes.

All right.

One second.

Okay.

Now, one thing I should mention to you is
that some of these groupings will have...

In order to relate the
problems, I favor joining

the problems, even if they
already appear elsewhere.

In other words, in some of the problems
that we're going to do, some of the

problems already appear in more than one
grouping.

But I still think it's useful to you.

One second.

Yeah.

Well, when we get to it, you'll see it.

But I still think it's useful in
discussion.

Even though there are some problems that
may appear twice in my groupings.

Because they have more than one thing
interesting about them.

Anyway, click and click cover.

The definition of a click is
a graph or subgraph such

that every vertex is
connected to every other vertex.

The user in the definition of a click.

The user in the definition of the problem,
it's not the definition of a click.

For the problem, and that's for CARPS.

I should say, for CARPS paper, because
that's the issue I mentioned before.

The user provides a parameter,
K.

That's not part of the definition of a
click.

But in CARPS paper, he
does that, and I mentioned

to you why, in order to
have a decision problem.

For CARPS paper, the user provides a
parameter, number K.

And the problem is to find a subgraph of a
given graph, G.

Such that there exists a click in G that
has less than... has K vertices.

So the graph has N vertices.

The graph or whatever subgraph that you
have has N vertices.

But now you want to find K of them,
such that there is a click.

Alright, fine.

Two questions first.

One.

How does the definition of a click differ
from the notion of a complete graph?

Which mathematically is the Cartesian
product.

If you take V, Cartesian product V,
every vertex is connected to every vertex.

And just so you should know, the complete
graph has the notation, all mathematicians

use the notation K sub
N, not C sub N, even

though the word complete
is a C and not a K.

Because the word C sub N is more generally
used for combinatorics.

And I don't think they wanted people to
get confused.

So a complete graph is less talked about.

So they delegated the letter K, which
sounds like K, even though it should be a C.

Anyway, K sub N is a complete graph N of N
vertices.

Right?

So the question is,

they're N vertices.

Complete graph.

And that's the Cartesian product V times
V.

Now, why is...

In what way does that differ from the
definition of a click?

What's the answer?

The answer is the key difference is the
word other in the definition of a click.

This implies, but not any edges going to
itself, which are called loops.

The complete graph has loops, vertices
going to itself.

Mathematically, that would be called...

In discrete math, we call that reflexive.

Look it up.

It's not something we need.

But, you know, it's going to yourself.

If everybody goes to itself in a
relationship, that's called reflexive.

Anyway, whatever it is, in discrete math,
you can look it up.

Okay, but a click does not require anybody
going to itself and doesn't care.

Doesn't consider whether or not anybody
went to itself.

It's only any other vertex.

Okay, that's the first problem.

The second one, the second question is a
little bit more subtle.

Searching for a click of k vertices seems
to be polynomial.

Now, that would be disaster.

Because if it's a polynomial algorithm,
then the entire CARP paper collapses.

That's what Cook...

Carp mentions this in
the introductory pages of

his article before he
goes on to the problems.

Cook already realized this as well.

Which is that if, in fact, a problem you
thought was NP-hard is actually could be

shown to be in P, then everything
collapses.

Then everything's in P. The hardness is
that this is as hard as that.

But if it turns out it's not, then the
other one's not either.

In CARP's definition for sure.

Because it's a two-way street.

And it's interesting.

And maybe only CARP's definition will
allow this situation, this discussion.

Because CARP makes...
requires you to prove in

reduction that the two
problems reduce to each other.

So that if one problem
is not... you thought

these two problems were
as hard as each other.

It turns out that one
of them is easy, then

the reduction shows
the other is easy as well.

Anyway, the bottom line is, why is it
easy?

Because what you have to do is choose K of
the N vertices.

Testing whether it's a click is just simply
testing the edges between each other.

All you have to do is take each node,
that's one for loop, go through each edge,

that's another for loop, and see,
does it go to all the other nodes?

That's straightforward to check.

And the choosing could
be... look at the math, could

be thought of as less
than or equal to N to the K.

So isn't that polynomial since K is a
user-defined constant?

So that's a serious question.

CARP obviously knew this, knew our
discussion, but what's wrong?

So this is a very cute, but sophisticated
answer.

Answer.

On line 81.

To a mathematician,
a constant is a variable

that did not change
throughout the process.

But to a computer scientist, a constant is
a variable that cannot change.

So it's through the process.

So let's repeat that.

A constant to a mathematician did not
change.

It had permission to change, but it did
not.

To a computer scientist,
it's not whether it did

or it didn't, it's whether
you don't allow it to.

It's true.

The permission is the difference.

To a mathematician is, did it change?

It could have changed, but you decided not
to change it.

I was lazy.

I didn't change it.

But it could have changed.

Right?

To a mathematician, that's a constant.

Practically, did it change or not?

To a computer scientist, I could make a
variable equal to 7.

And it's a variable throughout because it
could have changed.

It turns out I did not change it.

It was 7 the whole way through.

It's only a constant to a computer
scientist when I put the word final,

final, final, right, int, which meant it
cannot change.

I don't allow it to change.

That's a constant in computer science.

When the user gives the K, throughout the
given instance of the problem,

it did not change.

So that's why the question, because to a
mathematician, that's a constant.

But to a computer scientist, it's a
variable.

It's a user-supplied variable.

It turns out I decided
not to change it along

throughout this
instance of the problem.

But I could have changed it.

It would mess everything up.

But there's nothing that stopped me from
changing it.

You inputted a K into a variable.

That, to a computer scientist,
is not a constant.

It's a variable.

As such, the input K to CARP 3, the click
problem, is a variable and not a constant.

That's generating clicks is not a
polynomial, but exponential.

All right?

To avoid the confusion, mathematicians
will usually state, for a given K,

if K is a constant.

Mathematicians realize that this could
cause a problem.

So they usually will emphasize for a given
K, if a K is a constant.

But if a computer scientist, it's a
variable.

The fact that we did not change it
throughout our problem, and it's

beneficial to us that it does not change,
in terms of using it in the problem,

solving the problem, that does not make it
a constant to a computer scientist.

That's still a variable.

All right, so that's the click problem.

The click cover problem is even more wild.

The click cover problem is, if you were to
draw a graph on a really, really big piece

of paper, can one superimpose clicks all
over the place?

Such that when the clicks fall on each
other, you've reconstructed the graph.

So you want to deconstruct
the graph, but be careful

here, because they're
not mutually exclusive.

In other words, I could have
two neighboring clicks, one

on top of each other, with
shared vertices and edges.

For click cover, that's not a problem.

Deconstruction usually means independent.

But for this case, the reconstruct and
deconstruct is not independent.

You could have one click and another click
on top of it, which, when you put them

together, creates your graph, but the two
clicks have lots of things in common.

Anyway, can you reconstruct
a graph by superimposing

subgraphs of G, possibly
overlapping, that are all clicks?

Okay.

Note, the verification processes for these
problems are straightforward.

For CARP 3, simply check if edges exist
from any...

In other words, if the non-deterministic
machine for click would tell you these are

the K vertices that have a click,
you can check it, because all you have to

do is see if every node, every vertex,
every edge, double for loop, or whatever.

It's basically for loops.

For every vertex, check if the edges go to
all the other nodes.

For CARP 13, you would check if each... if
the non-deterministic machine said,

here are a bunch of clicks.

If you put one on top of each other,
you reconstruct the original graph.

How do you verify?

So first, it's as we
just said, to verify

independently that each
click is a click is polynomial.

And then just check if the union of
vertices and edges is the original graph.

So the verification is straightforward.

Anyway, the commonality is the word click.

That's 3 and 13.

All right.

Now, I guess we could do one more of the
last one.

Other than that, it's gonna... Everything
else takes a lot more time to discuss.

Anyway, in this one...

So here, the definition of directed and
undirected Hamiltonian circuit,

we already gave you here on lines 57 or
whatever, approximately, lines above.

Again, I added a line.

So it may not exactly be... It may be 56,
57 in the version I sent you out to you.

Okay, let's see if I'm doing it.

Let's say what they are.

Lines... Okay, there'll be lines 57
through 60... 57 through 62, about.

All right.

Or 63.

All right.

Anyway, directed and undirected,
Hamiltonian circuit.

Okay, we did that.

So just to remind you, circuit means
cycle.

Hamilton... I read Hamiltonian.

In modern parlance, we usually say tonian
as an adjective.

But anyway, Karp calls it Hamilton.

But a lot of people add the Ian...

You know... Okay, so just to be
consistent, I'll put Ian in parentheses.

But a lot of people say Hamiltonian.

Again, in Karp's favor, just as Hamilton.

Anyway, circuit means cycle.

Hamiltonian or Hamilton means every node
is involved.

Directed means that every edge only goes in
one direction in the drawing of your graph.

Undirected means every edge can go in both
directions in your graph.

Two-way street.

Now, mathematically, what you need is a
sequence of all the vertices.

And then you check it out.

Each node to the next, is there an edge?

And then the last node
in the sequence has an

edge back to the first
node in your sequence.

So, basically, the brute force exhaustive
search approach, if you were to take your

n vertices and generate all n
factorial permutations, which is

even more than 2 to the n,
greater than 2 to the n for most n.

But if you were to do that,
you will find the solution

to directed and undirected
Hamiltonian circuit.

So, the mathematical structure involved for
the exhaustive search is the permutation.

Now, there's job sequencing, which is
problem 19, all the way down.

He calls it sequencing because there
probably wasn't enough room.

But anyway, it's called job sequencing,
problem 19.

And job sequence, in shorthand,
is the following.

When one organized n tasks, n jobs,
in an order, in a sequence, such that,

in a sequential order, such that each
internal deadline is met.

Each task in the contract, you not only
promised your employer, or whoever's

paying, the funding agency, you not only
promised the funding agency that the

entire project will be complete by a
certain date, you promised them that each

task will be completed by a certain date,
and you gave the dates.

And you took upon yourself, this is Karp's
version, you took upon yourself a penalty.

If you do not make the internal date of a
given task, well, then you do not have to

pay me for that task, or whatever the
penalty is.

All right, you know, it's not
as drastic as don't pay me for

the task, but there's a penalty
associated with each task.

All right, so can one organize the end
tasks, the end jobs, in a sequential

order, such that each
internal deadline is

met, or no more, and
has no cost more than K.

In other words, it's not...

Normally, this would be an optimization
problem.

Okay, with all good intentions, we're
going to have to start this one next time.

So I'm going to tell you in the email, I'm
going to say we ended with click cover.

The reason it's the end of class,
and I don't want to do this just quickly.

I want to, you know, go through the
problem nicely.

All right, anyway, it's the end of class.

So if you didn't have a chance,
please text the word present.

Okay?

And I'll email you again.

The notes you have, I sent them last
night.

But I will...

What do you call it?

I will...

What do you call it?

Give me a second.

I will just tell you where we're up to in
the email.

All right, if you didn't have a chance,
please text the word present.

And we will continue with this on
Wednesday.

Thank you all.

Okay?

Thanks all.

Anyone else?

If anyone didn't have a chance,
please text the word present.

I haven't answered the word present.

Okay, Bye all!

Up, up, up.

See ya next week.