Text that you were present, and I'll set
up the board.

I don't know why, but logging in this
morning took a little extra time.

And an error.

This is great.

Let's do that again.

I've never had that before.

Let's try that.

Huh.

Wow.

It says there's an error.

Not sure why.

Let me try something else.

Let's see if I share the whole screen,
what happens.

Ahem.

Infinite loop.

Ha!

Okay.

Infinite loop when you share the screen.

Let's see if that works.

Not sure.

I'm not sure why that happens.

View presentations.

Stop sharing.

Okay.

We'll try again.

I've never had this before.

Um... Why isn't it allowing it?

An error has occurred.

Okay.

I'm going to log in again.

Give me one more minute.

I've never had this before.

Uh... I'll have to log in again.

You are currently the only person in this
conference.

What in the world is happening?

It's not allowing me to share the file.

Let me see if I save it.

Ah... Not allowing me.

It's not allowing me to share it.

Let me try a different file.

Let me close down Excel.

Let me open up Excel.

Ah, man.

Not sure what's going on.

Give me one more minute.

All right.

Good morning.

Let's see if it works now.

I restarted Excel.

Not allowing me.

All right.

Uh... We're going to have to do it really
old school.

Give me one second.

Let me, uh, create a new sheet.

New download sheet.

Uh, spelling spreadsheet.

Okay.

Let's see if we could do the following.

Um... How do I do this?

Share.

Something's funny.

Uh, share your... Okay.

Let's call the sheet.

One second.

Uh, okay.

Uh, okay.

Computer theory notes.

All right.

Let's call it notes.

Um... Let's share.

How do we share it?

Share to anyone with the link.

All right.

Copy link.

Done.

Okay.

Okay.

We're going to have to do something,
uh, very different.

I'm going to try one last time.

Uh... No.

Okay.

Let's see if I could share.

Oh, that's interesting.

Share notes.

Let's try this.

Oh.

It may have worked.

Okay.

Wow.

All right.

This is a little bit different.

What I did... Uh, first
of all, we all... Yeah.

Thank you.

What I did was that I, um, I
created... I don't know why.

All of a sudden it doesn't
like Excel, but I created a

arbitrary Google Sheets,
which I'll transfer to Excel.

At least we have something, uh,
just to deal with.

It looks a little small.

Let's see if I could, uh, get,
um, better the size.

How do we increase here?

How do we increase size?

View?

I don't know.

I haven't used... Oh, wait a second.

What's this?

Add sheet.

Why can't I have, uh, increase the size?

How do we increase the size?

Why am I not having access?

Hold on.

Oh, there we go.

Where do you, um...

Oh boy.

Increase size.

Well, can you read this?

Let's see that.

Wait, let's see.

I got an idea.

I guess if I use a higher font,
uh, view... What's this?

10?

Ah, good.

All right.

So let's use, uh, 20, 24.

All right.

Good.

Let's see if that... All right.

Good.

All right.

Uh, can you see... Can
you read the screen?

Text in the, uh, chat if you can read the
screen.

Good.

All right.

So we'll start with that.

All right.

So, uh, due to, uh, thank you.

Due to some technological, uh,
well, logistics really, um, we're going

to, uh, hopefully have a review today.

So, um, let's, let's first open up.

I'm going to open up the syllabus just to
make sure.

I'll, I'll write down with you the topics
that should be on it.

So let's be clear what the topics of the
quiz are.

Oh, wrong, wrong one.

Great.

We'll use the wrong one.

All right.

Uh, 2026.

It's a little technologically a little
bumpy today, but we'll get there.

Uh, let's do this.

Um, okay.

Syllabus.

Good.

So the last quiz was on, uh, the last
thing we did.

Oh, yes.

So now the question was, uh, CARP 21.

So the, okay.

So we have, oh, we have a bunch.

Um, so the, uh, we
have not done, I think we

ended with the
mathematical structures, right?

I believe so.

So that means that CARP, all of CARP 21,
P equal NP, and primitive recursive.

Okay, good.

So let's say that.

So, um, uh, uh, uh, okay.

Syllabus topics on quiz.

So we have, uh, CARP, CARP's paper,
which includes, uh, P equal NP.

Uh, we have the notion of non-determinism.

Uh, sorry.

What else do we have?

Uh, 21.

Okay.

So we have Cook's, uh, Cook's,
uh, initial, okay.

Satisfiability.

Then we have CARP's 21, although again,
it's really 20, because,

uh, one of the 21 is Cook's.

All right.

And then we had, uh, three definitions for
reduction.

We talked about the, uh, components of
reduction.

So it's what does that
entail, especially, especially

when applied to the
reduction tree in CARP's paper.

Is that page 96, I think, uh, of CARP's
paper?

Okay, so we had that.

Um, and then we had primitive,
we had, uh, well, beginning notions of

recursion, but, uh, okay.

Primitive recursion.

We had about approximately 16 different
mathematical functions.

Maybe more.

16 to 20, I don't remember.

Approximately six, uh, approximately 16
different mathematical, uh, functions,

uh, defined.

Missing an R here, spelling.

Then what?

Give me one second.

Uh, oh yes, okay.

Leading up to bounded minimization.

Um, just to give a... we're gonna have to
discuss this a little more in a different

class when we come back from the spring
break.

But just to give a, uh, conclusion of,
of our whole leading up discussion.

What, but...

What Davis realizes...

From this...

Is that a version of minimization,
a version, not bounded.

A version of minimization, uh, is what
is missing, uh, from the formulation.

..

Of primitive recursive...
Of primitive recursive...

To cover...

Or to implement...

All...

Mathematically computable functions.

Okay, that's what's missing.

A version of minimization.

Uh, yes.

Now, one, one little point we said,
uh, was...

Okay, let's, let's add one, something here,
which is that, um... Um, Ackerman's...

Function...

Was used... To prove...
That, uh, primitive recursive...

And not... Model all...

Computable functions.

Okay?

So that was that case.

What Davis realizes is that a version of
minimization.

Uh, so let me just tell you what that
version is.

Uh, so the version of minimization,
just to complete our... Lead-up.

And this is the last sentence of the
material, uh, that you're responsible for.

But the, the lead-up is that, um,
unbounded minimization...

Is what is necessary.

Is the technique missing?

From the primitive recursive formulation.

Okay?

Unbounded minimization.

Uh, and it is not the simple initial
functions that, that is, uh, lacking.

Unbounded minimization.

And the new uh, that are lacking.

So... We start now.

Remember, the risk chip.

I guess we should add that to our
discussion here, which is that,

um...

Um... One second.

Davis is trying to formulate a risk
approach, reduced instruction set computer

approach, to mathematically model all
computable functions.

That was the idea.

So we went through 16, Davis does more,
but Davis does more than this,

especially with prime numbers

and encodings, which we
will discuss in a different

class, which we will
discuss in a future class.

But we didn't need it for what?

We didn't need it for our discussion now.

But for now, only these were necessary.

Only these approximately 16.

I'll check how many there are.

OK, so he started out with this with this
system leading up to bound minimization.

But then what Davis realizes is that
something's missing.

All right.

That's what he realizes.

But Davis realizes that something is
missing.

OK, and what's missing?

So the answer is unbound minimization.

Unbound minimization is what's missing.

In other words, bound minimization,
so just let's define it.

Bounded minimization

finds the first time, we'll call it index
or input, that a predicate is true.

But bounded over a range of numbers.

And that's the bound.

OK, bound minimization
finds the first time that

a predicate is true over
a range of numbers.

That limitation is too restrictive.

This range limitation is too restrictive
for defining all computable functions.

If

we drop the range.

If we drop the range and ask for the first
time ever that the predicate is true,

then all computable functions can be,
all computable functions can be derived,

can be derived from
primitive recursive definition,

plus adding in the
unbounded minimization.

Now, there obviously is a technical
problem, and Davis knows that.

But that just, in essence, gives us a
further slight definition, right?

An issue can arise because
how do we know ahead of time

that an arbitrary predicate
actually is true anywhere?

We don't, not for an arbitrary,
I mean, that's all, it's very hard to do

unless you plug in every value,
every input value.

So this further leads Davis to realize
that

not only, not only does primitive
recursive definition, plus now unbounded

minimization, yield the definition for all
computable functions.

It also, when, okay, so, and I'll clarify
this in a second.

This also yields a definition for all
partially computable functions.

Okay, so, so, in essence, the,
what, what turns out is that the partially

computable functions are going to be
precisely where some Boolean predicate is

never true, and you just, and you don't
know that yet.

That's the infinite loop that you'll never
be able to figure out unless you try every

possible number, but of course there's an
infinite amount of possible inputs,

or a crazy amount anyway.

This also yields a definition for all
partial computable functions.

Let me just stay for a second.

Give me one second.

Yeah.

The partially computable function,

function, can, just to remind you,
can go through an infinite loop

for some possible, for some possible
input.

Okay.

If one were to mathematically
model this particular

function, so you have some
partially computable function.

If you were to mathematically model this
particular function based on primitive

recursive, based on the improved, based
on the, not approved, what would you say?

How do you say when you add something?

Based on the enlarged, no, oh boy,
what's the word?

Not elongated.

Based on the expanded.

Okay.

This particular.

If one were to mathematically model this
particular function based on the expanded

notion of primitive recursive,
which includes, what do we say?

Which includes unbounded minimization.

Again, Davis calls this version a PRC,
which stands for primitive recursive class.

Remember?

He knew that something was missing.

And if he figures it out, it's going to be
based on primitive recursive.

So to keep it within the family,
he still wants to give it somewhat the

name of primitive recursive,
but he can't because

it's something extra
that's not really part of it.

So he calls it a primitive recursive
class, PRC.

And that's in this book.

So this particular function based on the
expanded notion of PR, which includes

unbounded minimization, will correspond to
a definition based on this PRC,

where it includes an unbounded
minimization,

which never actually achieves a true
value.

I'll deal with the screen in a second.

Which never actually achieves a true
value.

That is equivalent to the infinite loop.

I know about the screen.

Give me two seconds.

I'll change in a second.

That is equivalent
to the infinite loop that

this partially computable
function experiences.

That this partially computable function
experiences.

If one could guarantee that the unbounded
minimization always holds,

i.e., the, give me a second, the predicate
does have at least one set of inputs that

becomes true, that the predicate is true.

It's true on.

Give me a second.

Okay.

Then...

Then this PRC development...

We should do it that way.

Primitive recursive...
He doesn't put the dash...

Well, because I want to emphasize that
it's based on primitive recursive.

We're just doing this extra piece.

But all right.

All right.

Then this PRC approach will yield
all... Will yield computable functions.

Okay.

So whether the... Again,
primitive recursive is n, s, and u.

Which is the null function, n of x equals
zero.

The successive function, s of x equals x
plus one.

U, which just returns a value from a list
of values.

And then you have two techniques,
composition and recursion.

If we throw in unbounded minimization,
you stay within the fold.

You stay within primitive recursive.

If you add unbounded minimization.

If you could guarantee us that the bounded
minimization always halts.

Meaning that the Boolean predicate that
you're going to use...

If you could guarantee us that the Boolean
predicates that you're going to use...

Will always yield at least once a true
value for some set of inputs.

Then throwing that into the mix of n,
s, and u, composition and recursion...

Will yield all computable functions.

If you consider all possible predicates,
and some of them, or a number of them,

may not be true ever, and you throw that
in, but you don't know that, and you're

throwing that in as the mathematical model
of your function, so then, in fact,

you will get the partially computable
functions, okay?

So let me summarize
that, and that concludes

our discussion up to
the point for the quiz.

It also concludes the topics, and we'll go
back and discuss them, of course.

But, one second.

Okay, good.

I don't know if you see.

I'm just curious.

My screen blinked.

Can you tell me if your screen just
blinked?

Did anyone have a blink in their screen,
or is it just mine?

I know why it blinked, but I'm just
curious.

Was that my
interaction with the virtual

classroom, or was it
just my personal screen?

Did anyone else have a blink a second ago?

Anyway, fine.

No, good.

Okay, so it's just mine.

That's fine.

It has to do with my switching
from the notes back to the

chat, and the switching
takes a second, so it blinked.

Anyway, not important.

So, thank you.

In summary, primitive recursive.

Okay, let's say NSNU with composition and
recursion, the way we've defined it so

far, will produce all,
well, by definition,

produces all primitive
recursive functions.

Okay, that's by definition.

That's not the great statement.

The point is, and does not, and does not,
that's the key part, from Davis' point of

view, and does not compute all,
or does not produce all computable,

or even partially computable for sure,
but all computable functions.

Okay?

And that's acronym as a proof,
cross-reference acronym.

Okay, which grows faster than any primitive
recursive function can possibly grow.

All right, that's the case.

But, NSNU with, okay, and what we
concluded last time was, and this is the

case, even with bounded minimization,
which is a powerful technique,

but it's not, it does not take you out of
this family.

Okay, so that's the first point.

Okay, so that's the first point.

Okay, now comes the second point.

The second point is as follows.

NSNU with composition, and recursion,
and unbounded minimization,

where if you can guarantee,
or where if it is guaranteed

that the Boolean predicate
has a true value somewhere,

where, then that will produce,
will produce all computable functions.

Then, third,

NSNU with composition, and recursion,
and unbounded minimization, where if it is

guaranteed on line 48 here, it is
guaranteed, or that it can, it is not

guaranteed that the Boolean predicate has
a true value for some input, will produce

all partially computable functions.

In other words, if it's possible that some
predicates will not have, that you're

going to use some predicates, you don't
know this ahead of time, but some of the

predicates will not have a true value,
that will produce your infinite loop

experience, because it's checking,
and checking, and checking, and there is

none, and it can't prove it.

So, then that will produce all partially
computable functions.

Okay?

So, that is the summary, and that's where
we're up to till today.

All right, let me just drink something.

All right, would you want...

Please, if the... I'd like to open the
floor to the students, in a sense.

Would you like me to go over...

We did a lot of different things.

Would you like me to go over any...

Anything for the...
What you call it?

For the quiz.

Let me just open...

Because in case you ask, I want to...

We did... I mentioned...
Yeah, we did do it.

Okay, fine.

Oh, yeah, I should add that.

I'm sorry.

Let me... I'll add that to
our list of topics in a second.

Let me just open up CARB's paper.

Let me open up CARB's paper.

In case you want to ask something,
I want to refer to CARB's actual paper.

And then we open up another thing.

The tree.

I have a separate thing for the tree.

It just makes it a little bit easier to
refer to the tree.

Okay, excellent.

Now, let me get back here to
where my notes are... Where you are.

Okay, what did I want to add?

Yes.

Okay, I have to add one more thing.

One second.

CARB's paper.

Yes.

Well, okay.

So...

Let me do this first.

Hold on.

In the order of CARB's
paper, you first need

the definition of
non-determinism, equal MP.

And then here...

Well...

Cook... Oh, not Cook.

CARB presents... And we
elaborated in the notes...

Tweaked problems.

Slightly changed problems.

That... Are in P...

With similar problems in MP.

Okay?

The CARB presents...

And we elaborated in the notes...
Tweaked problems that are in P...

With similar problems that are in MP.

All right.

So that... That we have.

And in the notes, we added some.

But CARB passed that in the beginning of
his paper.

Okay, good.

All right.

So I open the floor in case anybody has a
specific question...

That you would like me to go over.

Anything... Any one
of CARB's 21 problems.

Any of the P problems.

Anything you'd like me to go over.

Anything you would like me to go over.

Well... Let me see.

All right.

Let me ask you right now.

I want you to text.

I want you to think about and text the
following.

I'll rattle off some questions.

And you tell me what you think the answers
are.

Please refer to the names of CARB's
problems.

It's okay if you don't remember the exact
name.

As long as we get the gist, that's fine.

Don't just cite the numbers.

Because it's... Unless
everyone has all the notes open...

They won't understand it.

What the numbers are.

So please refer to the actual names of
problems.

All right.

Which of CARB's problems...
I would like you to text.

And you text one at a time.

Instead of one does one, one can do
another.

Which of CARB's problems are related to
cycles?

So kindly text.

Well, that... So that...

The whole paper deals with NP complete.

But I want the actual names of CARB's 21
problems.

Which of CARB's 21 problems refer to
cycles?

In their definition.

Okay.

So Lauren mentions two of them.

Happens to be number seven and eight in
CARB.

Feedback note set and feedback arc set.

Good.

So while...

There's more.

But while you're
thinking... I'm gonna text it.

Let me say what the definitions are.

So feedback note set and feedback arc set
are similar.

We want to
know... First of all...

Assuming you could identify...

Which we don't know how.

But it turns out you don't need it.

But... Assuming you could identify
all the cycles that exist in a graph.

Okay?

All the cycles that exist in a graph.

So... And they could overlap.

In other words, within the cycle,
an edge can't be written twice.

But...

You can't... You reuse an
edge or node twice in a cycle.

But two cycles can share the same edge and
share the same...

Similar vertices between two cycles.

Anyway, so they could...
The cycles could overlap.

So the question is...

If you consider all cycles in the graph...

Could you find, in the case of node set,
some vertices?

In the case of arc set, some edges?

That, in some sense, represent all cycles.

How do they represent?

That the cycles have something in common
with that set.

They have at least one edge in common,
or in the case of arc set...

Or they have at least one vertex in
common, in the case of node set.

And that's the question.

Can you find such a set?

Now... If... If we just state it
that way, it's a trivial problem.

Because consider all edges for the arc
set.

Consider all original edges for the arc
set.

Consider all original nodes for the node
set.

Right?

So that's ridiculous.

Obviously...

If you have everything, so then obviously
you're covered.

Right?

All cycles have to use something there.

So what makes this a hard problem is that
you restrict it.

You set a limit on how many vertices in
the node set...

Or how many edges in the arc set you're
allowed to use.

That's what makes it a hard problem.

Okay.

So those are two.

Two... Good, Lauren.

There are more.

That's not the only answer.

What are names of other problems in CARP
21 that deal with a cycle?

Yes.

Great, Lauren.

That's correct.

Problems 9 and 10.

Directed and undirected Hamiltonian
circuit.

So although it may not be obvious if you
didn't remember from the lecture,

in older English, the word circuit meant
cycle.

It means a cycle.

I think I explained to you why it's called
a circuit court.

The circuit court was that years ago,
the small towns didn't have enough people

and funding to have a court.

So they used to have a
court that would cycle circuits,

that would go from town
to town and come back.

And they would do this on a monthly,
weekly, I don't know exactly their

schedule, but on a regular basis.

So that was called the circuit,
circuit court, literally.

It was a higher level court.

In other words, you have the local
townspeople who adjudicate, and then the

circuit court would review the findings of
the local courts.

So that was a higher level court,
the circuit court.

And that name stuck even until today.

Okay.

They don't move around,
but the higher level

court is sometimes
called the circuit court.

Anyway, circuit is the cycle.

Hamiltonian, Hamilton or Hamiltonian,
means that every node of the original

graph is involved in your cycle.

Correct.

And so we're only
dealing... as opposed to the

feedback node in our set,
you're involving all cycles.

In the case of directed
and undirect or undirected

Hamiltonian circuit, you're
only involving one cycle.

A cycle that involves... that is made
up of... comprised of all the nodes...

all the nodes of
the original graph.

Directed and undirected because your graph
could have directionality, right?

Vertex one goes... it
goes to vertex two, but

not necessarily vertex
two goes to vertex one.

That's directed.

Undirected means it's a two-way street.

If... if vertex one
goes to vertex two, you

could cross over, come
back on the same edge.

Vertex two goes to vertex one.

It has no directions, no arrows.

So in both of those versions, it's empty
heart.

Again, why did... you know, it's a little
bit funny.

I mean, well, we're not... we are not carp
and we're not cook.

But, you know, just from an innocent point
of view, what's the big deal?

Directed, undirected?

It's a graph, right?

So carp was very careful because of
what... again, page 89-90, where he...

and we elaborated,
which is that...

you change the problem slightly, you risk
changing easy to hard and hard to easy.

So because of that, he's not... he's not
taking chances.

So he wanted to change it
from directed to undirected

or vice versa, whichever
version he did first.

And then he said, you know something?

I'd better prove it again.

Because it's not always
obvious that a simple change

we think is simple may
actually change everything.

Right?

So that's the case.

Now, a little bit more interesting note
about the feedback set is that although

the definition requires knowing all the
cycles, the actual verification of your...

let's say the NP computer,
the non-deterministic

computer tells you
the answer, right?

That's its purpose.

To tell you the answer instantaneously,
give you the answer of what's in your note

set or what's in your arc set,
now you have to verify it.

You're not going to use it, right?

You know, even if you
have a really smart dog

spot and you ask a spot,
should I invest in IBM?

Ruff, ruff, ruff, right?

And should I invest in Apple?

You know, whatever.

And then, you know, it moans if it doesn't
like the stock for some reason.

And it barks if it likes the stock.

And you believe that it's responding to
you when you asked it should you invest.

I don't personally advise you listening to
what your dog's going to respond when you

ask it to invest.

But in the story, someone did that,
right?

So I don't know if you should... even if
it turned out that, you know, the ones

that you got, that you invested,
and worked, I don't know if you should

necessarily think that spot knows the
stock market, right?

You want to verify the solution.

So that's part and parcel of this process.

That the non-termistic computer gives you
all the information, but we, the human,

isn't going to use it until we verify that
it's a good solution.

So how are we going to verify
feedback node set and arc

set when it's a crazy hard
problem to generate all cycles?

So Karpu in his genius says that to verify,
you don't need to compute a single cycle.

What you need to do is the following.

If it were true that you had a feedback
node set, the vertices, that's every cycle

has shared something in that set,
or you have an arc set, the edges,

where every feedback arc set, where every
cycle shares something with that edge set.

So then if you, if the non-termistic
computer gave you one of those sets,

delete it from the original graph.

And because you claimed that every cycle
had something in common and now you

deleted it, you broke every cycle.

Now every cycle is missing something.

It's no longer a cycle.

It's missing a node.

It's missing an edge.

Whatever was common with your feedback
set, right?

So now you have a graph that has no
cycles, if you did it correctly.

If you did the feedback set correctly,
or if the non-termistic computer did it

correctly, so then you, when you delete
it, you have a graph, a subgraph,

that no longer has cycles.

To test whether a graph does not have
cycles is actually polynomial.

And there are many ways to do it.

Depth-first search, breadth-first search,
there's just so many ways.

Actually, breadth-first search is the
better way.

They're just topological sort.

They're just matrix approaches.

There are a number of ways to do it.

Anyway, so that's an interesting little
tidbit about feedback.

Good.

All right.

Let's continue our discussion here.

How... which problems... again,
give the names.

Which problems deal with packing?

Oh, okay, well, that's true.

I was gonna elaborate.

Okay.

Let's elaborate.

Let me elaborate.

Oh, you know, let me say it that way.

Which problems deal with packing?

Okay.

I said it.

Let's say it that way.

When I write the notes, I'm gonna summarize
all of this interaction right now.

It's straight from the
notes, but I do want to

make a complete set of
notes that I'll email you.

Okay.

Well, you...

Yeah, I'll send you the...
What's your problem?

I'll send you an Excel exactly of
what's... of these notes.

Or I guess I could send you a link.

Anyway, either way, you'll get the notes.

All right.

So... Okay.

So which of CARP's 21 problems deal with
packing?

Packing something up.

Okay.

Excellent, Lauren.

Very good.

Good.

Set packing, set covering, exact cover,
and knapsack.

Excellent.

They all have to do with packing.

In the case of the first three...

Okay.

Let me ask you, Lauren.

You seem to be involved.

If you don't mind, I'll have...

You'll be the representative.

Not putting you on the spot.

But if you enjoy this interaction,
so then please feel free.

But anyone else can jump in also.

So what distinguishes...

It's true.

Your answer is 100% correct.

What distinguishes the first three from
the last one?

In terms of the story of packing.

What distinguishes set
packing, set cover, exact

cover, versus knapsack
in terms of the story?

Of packing.

There is... Even though...
Yes, they're all packing.

But there's a difference in the story.

What differentiates the story?

Excellent, Lauren.

Very good.

Correct.

In the case of set
packing, set cover, and

exact cover, the story
is you already packed.

And now the question is, you don't want to
unpack.

The question is which boxes, which groups
to take with you.

Right?

In the case of knapsack, you have not yet
packed.

Correct.

Excellent.

Very good.

So, why are there so many different
versions?

That leads to the notion of a partition.

A partition of elements...

You have a bunch of elements.

Now, in the classic
definition of a partition,

it's on sets, which means
there are no duplicates.

Okay?

Obviously, if you're
packing your own stuff,

you probably have more
than one pair of socks.

But in the case of
packing, in case of

partition, that would
not technically be there.

They would be all distinct.

Anyway, we could just
modify it by saying, you

know, blue socks,
green socks, I don't know.

Right?

Something like that.

But anyway, so, whatever the case may be.

But let's ignore that for a second.

So, the partition has some essential
ingredients.

The definition of a partition is that
every element is packed.

And, of course, no other elements.

You didn't put in someone else's stuff
with yours.

Then, also, you can't have duplication.

And, again, meaning when you group them
into their subgroups, into your boxes,

and you write the inventory on the boxes,
because, as I said a second ago,

technically a partition is on sets, so you
can't have duplication between the boxes.

Okay?

Okay?

So, that if you were to look at the
inventories on one box and compare it to

the inventory on another box, they can
have nothing in common.

So, they're mutually exclusive.

So, that's another ingredient.

All right?

You can...

And you have
to... Well, if you...

Now, there's another technical little
point, which mathematicians make,

but that's really in labeling,
not in the part of definition,

which is, were you told ahead of time how
many boxes to use?

If you were told ahead of time to use K
boxes, then you call it a K partition.

If you were not told ahead of time,
and you have the luxury to decide how many

boxes to use, that's just called
partition.

Okay, excellent.

So, the case of set packing versus set
covering.

So, in the case... To cover
means that everything is included.

All right?

To cover means, in general, in mathematics,
a cover means everything is included.

So, packing, set packing concentrates on
the mutual exclusivity.

That you're going to take a certain amount
of boxes.

Right?

The example I gave
you was the trucker says,

I can only put so many
boxes into my truck.

Right?

You're going to this trade show in Vegas.

And you're taking your wares to display.

And you want to make some big sales in a
trade show in Las Vegas.

Right?

So, the warehouse people packed all the
boxes, packed the whole warehouse.

And now you only allow a certain number of
boxes.

And you don't want to undo it,
because it would take too long.

So, you read the inventories.

And now, set packing,
problem number four,

you're going to pick
mutually exclusive boxes.

That the boxes... each box has nothing to
do with the other box.

But you're not necessarily going to get
one of every... of the original elements.

That's set packing.

Set covering.

Oh, you're right.

It's actually called set covering.

Thank you.

The ING.

Because sometimes he only uses the word
cover.

Like node cover and exact cover.

But here it does set covering.

That's interesting.

He may have
purposely... Problem six.

He may have purposely
done that so that you

would immediately
connect it to set packing.

The ING.

I wonder.

He may have done that purposely.

Set covering is that of
the boxes you choose, you

want to make sure that
every element is there.

Now, again, this is because you can't...
in this case, you can have duplicates.

Right?

In the case of a warehouse, you have many
hammers and many screwdrivers.

Right?

And many drills, etc.

So, when you pack,
when the workers pack,

the boxes are going to
have things in common.

Each box is not mutually exclusive.

So, in other words, it could be,
but you're not expecting it.

So, set covering wants to make sure that
the boxes you select, the minimal amount

of boxes you select, the K boxes you select,
that all the elements of the original.

..

At least one of each of the original
elements is in your boxes somewhere.

But you don't worry about being mutually
exclusive.

There will be duplicates.

So, that's number six.

If you want both, that's exact cover
number 14.

So, they packed everything.

The word duplicates.

You want both.

You want your cake and eat it.

You want that the boxes
you choose to put on the

truck are... have nothing
in common with each other.

Mutually exclusive.

And you want that all the boxes together
have one element of...

You know, it has one representative of
each thing you make of the original items.

No duplicates and one element of each.

So, that's called exact cover.

In the case of knapsack number 18,
clearly, you can't take everything.

You have an upper limit on weight.

You're traveling.

You're traveling.

And the airlines have a limit,
whatever number of pounds it is.

And you don't want to go over.

But at least in your advantage,
and that's the assumption in Karp's

definition, that you actually need the
max.

Right?

Because an extra, you know, can of food.

An extra book.

An extra pair of shoes.

A shirt.

Whatever.

That would be useful to you when you're
traveling abroad.

Right?

Because you have more of your items
available to you.

So, knapsack assumes that you're going to
maximize, but not go over.

There will be penalties.

Karp doesn't talk about the penalties.

But the fact is you don't want to go over
the items.

Good.

All right.

Now, let's think.

Which of Karp's problems...

And again, give the names.

Which of Karp's problems
deals with partitioning

some sort of original
set into two groups?

Which of Karp's original problems deals
with splitting the elements into two groups?

Give me the names of Karp's original
Karp's problems that deal with the

definition deals with splitting into two
groups.

And one of them hopefully will be obvious
to you.

After I say it, I think you'll find it's
obvious.

Right.

Thank you, Ria.

You're correct.

Partition.

Partition is the mathematical notion of
partition, but the constraint that Karp

adds is that the sum of the values in each
of the groups, when you add them up,

they equal each other.

Now, while modern versions of Karp's
problem 20, is it?

Karp's partition problem, you know,
number 20, while modern versions have K

partition, that you do
the same thing for K

subgroups, Karp's
original definition is two.

So that is correct, Ria.

Partition.

Partition.

Number 20.

Okay.

There's more.

What's another problem
that the definition is

defined by dividing some
sort of set into two groups?

Oh, good, Lauren.

Excellent.

Max cut.

Exactly.

Thank you, Lauren.

Sorry.

Max cut.

Beautiful.

Now, what's max cut in problem number 21?

Max cut.

And that's a very important problem,
Max cut, in modern network theory.

Max cut is the following.

Imagine you're dealing with fiber optic
cables between, you know, two different

areas that your company is providing
service for.

Communication, internet, phone,
whatever.

Media, whatever you're providing
communication with, for.

Anyway, so there are basically your
network is in fact a graph, right?

So there are central towers,
or maybe they're the individual

people, and then everyone's
connected to somebody.

And that's how the communication is made.

Things are passed along from cell tower to
cell tower, or from, you know,

node to node in your network, whatever it
is.

And let's say there's a traffic,
meaning your network analysis tells you

which cables, which edges have a lot of
data, which edges have little data.

So you know how much bits, how many bytes
are being passed along the cables.

Okay, now the issue, the
concept of max cut is you

want to figure out the most
vulnerable set of cables.

You want to divide your network into two
groups.

And only consider the edges between the
groups.

Inter, but not intra.

Intra means within the group.

Inter means between the groups.

So you only want to consider between the
groups.

Okay?

So that...

So between the groups, good.

And the idea is, well, how much...
And they're all possibilities, right?

It's not...

We are not considering Queens and Manhattan
where the two sets are well-defined.

We're considering any two groups,
any subset of nodes.

So you're partitioning every node in your
network into two groups, even if they're

not geographically near each other.

But just because there's a cable
connecting them.

So you divide into the nodes in your
network into two groups.

There's... There's an
edge between the... From...

From the nodes in one group to the nodes
in the other group.

If you add up all those
edges, that is the... That's...

For our purposes, it's called the cut.

Being that if somebody were to cut those
cables, you will...

The sum will tell you how much data cannot
be provided anymore.

And max cut is to...

Figure out which two groups has the most
data between them.

Right?

When you sum up the loads of all the
cables between those two groups.

And that's called max cut.

Good.

That's also a two partition.

So the problem 20 and 21 are both two
partitions.

Okay.

One more problem is a partition,
but it's not necessarily a two partition.

Which other problem is a partition,
but not necessarily a two partition?

Which other problem
in CARP's problems is a

partition, but not
necessarily a two partition?

Okay.

Let's see if you get it.

Excellent, Lauren.

Chromatic number, exactly correct.

Chromatic number, in essence, is a K
partition.

You have a graph and there are nodes and
there are edges, vertices and edges.

And you want to paint the nodes.

You want to paint the nodes such that if
there's an edge between two nodes,

then the colors of those nodes comprising
that given edge are different.

Right?

I gave you the story, which was... it's
true.

I heard it personally.

No.

I wasn't there.

But I heard a clip of an interview of
Taylor Swift.

So she was building some sort of ranch
somewhere in Texas.

And she said that she wanted the following
cute little thing in her kitchen.

That all the cabinets in the kitchen,
there are two doors.

And the... and first of
all, the knobs had to have

some sort of icon of
something related to the kitchen.

So one knob will be
in the shape of a fork,

one knob will be in the
shape of a spoon, etc.

But the knobs that are connected in the
two doors have to be different.

And that was her... what she thought was
cute in her kitchen.

So she was... that is chromatic number.

You're given ahead of time a certain
number of paint.

And you paint the nodes in your graph such
that if there's an edge between those two

nodes, the nodes have to have different
colors.

So because you're given K paints,
K colors, K paints.

Chromatic means color.

So a number means the number of paints,
chromatic number.

So you're given K paints.

And in essence, it partitions the nodes
into K groups.

What's the binding commonality of the
group?

That they all are painted by that given
color.

So nodes 2, 3, and 5 are blue.

Nodes 3, 7, and 8 are red.

And another one's green, etc.,
etc.

So that in essence divides all the nodes
into K partition.

Excellent.

Now, there is another problem,
but I would not include it.

Because the definition is not worded in
terms of two groups.

And that is knapsack.

While it is true that you put some items
into your knapsack and not all items are

in your knapsack, the partition... that's
not a...

I do not include it because
the ones that are not were

part of a big set that
included the ones that were.

It happens that when you're done,
there are those that are in your knapsack

and there are those that are not in your
knapsack.

But that's not the purpose of knapsack.

Knapsack is you
have the union of all the

items and then you
pull out a subset of them.

So knapsack I would not include into this
discussion.

Very good.

Very good.

Which of Karp's problems...

The name of the problem
sounds like the opposite

of what you're actually
trying to achieve.

Which of Karp's
problems... Are you...

While you're saying the chromatic number,
let me look it up.

What's number 12?

Which of Karp's problems...

Is the name of the problem...

Seems to be the opposite of what you want
to achieve.

Alright, vertex covers.

..

Ah...

Alright, so Ria, I think I know what
you're driving at.

So let me reword what I was trying to say.

I think what Rhea was answering was the
following.

It is true, Rhea, that Karp in his paper
has a different problem, arc cover,

edge cover, which is a P problem, whereas
vertex cover or node cover is an NP.

But what I was referring to doesn't deal
with that distinction.

I mean that the problem itself alone,
what you're trying to accomplish,

actually seems to be against what the name
of the problem is.

So that was a good suggestion,
but the problem I'm interested in,

the definition of the problem seems to be
against what you're trying to achieve.

In vertex cover, it does involve nodes.

By vertex cover is that all you have a
representative group of nodes where every

edge has something in common with those
nodes.

So all the nodes are involved.

I'll just give it a little more time.

Again, anyone who just walked in,
as it were, one of Karp's problems,

the name of the problem, in essence,
is...

The definition actually
seems to be against that

which the definition
seems to try to achieve.

In other words, the name is
different, seems to be different

or against that which the
definition seems to require.

Anyone?

Last call?

Nope?

Okay.

Let me check up the problem number.

It's problem number 17, three-dimensional
matching.

The reason why I say that the definition
seems to be against is that when you line

up your lattice points, let's say
three-dimensional points, X, Y,

and Z, when you line up the T,
the letter T, that's what he uses,

the T points, X, Y, Z
points, and you line them

up, and you look at the
dimension by dimension.

You look at all the X sub X part of the
points.

Then you look at all the Y dimension
points, the parts of the points.

And then you look at all the Z part of
those points.

None of those numbers can match.

So the three-dimensional
match is called a match, even

though what you're really
hoping for is that nobody matches.

That there is no
commonality between anybody

when you list the T
points within the dimension.

So that would be problem number 17,
three-dimensional matching.

All right.

If there are others you want me to go
over, you know, say as well.

I will now try to jump into a slightly
different part of it, which is the P,

the tweaked problems.

All right.

So I'm going to mention the NP hard
problem, and I want you to mention a

similar P problem.

Okay.

So problem number 20,
knapsack... I'm sorry, not 20, 18.

Problem number 18, knapsack is NP hard,
but a tweaked cousin is NP.

Which cousin is NP?

Knapsack is NP hard, but a tweaked
problem, fractional knapsack.

Excellent.

And the example traditionally given are
people who sell spices, right?

If you're taking spices to Las Vegas and
you're carrying them or putting them in

your bag, and you're four ounces over,
I think I told you the shoe story.

It's a true story where I
was, you know, like, I don't

remember how many
ounces over the 50 pound limit.

And I won't tell you which airline or
which airport for that matter.

It was in America, but whatever.

I don't want to... Anyway,
whatever, it's not important.

But anyway, so they made
me hold up the whole line, and

they wouldn't take my
luggage till I took out one shoe.

They really made me do this.

And then it was exactly 50 pounds,
and then they accepted the luggage.

And then I think I told you, I asked the
person behind the desk there, I said,

well, what am I supposed to do with the
shoe?

So she says, well, carry it on.

So I said, you know, you
do realize that in terms of the

amount of gas the plane's
going to use, it's the same amount.

It's the same weight,
whether the suitcase is on

the deck below with the
luggage or on top, you know.

Anyway, that's what they said.

So that's what I did.

I put a shoe in my coat pocket and I went
on with the shoe.

All right.

Anyway, good.

At least I didn't have to throw it out.

So I'm happy.

So fractional knapsack.

So in case of spices, it seems to be that
if you're a little bit over...

If it's over the limit, you could just
pour off a little bit, right?

Not a big deal.

So it's three quarters of a pound of
garlic.

Okay.

But everything else you have, you're going
to move on.

Good.

All right.

We mentioned three dimensional matching.

Number 17.

3D matching is in NP, NP hard.

Which cousin tweaked problem is in P?

Fractional knapsack, CARP doesn't mention.

This one, CARP does mention.

So which page 89 and 90 of his paper.

So three dimensional matching is NP hard,
NP complete.

Ah, excellent.

Oh, you even did both names.

I thought you were going
to give one name and

then I was going to ask
you what's the other name.

You correctly said both names.

Two dimensional matching, which CARP
actually calls bipartite matching.

Excellent.

Where instead of lattice points having
three dimensions X, Y, Z, you only have X

and Y in the number plane.

Very good.

Excellent.

Okay.

Let's deal with another one.

Well, before, Ria mentioned node cover,
also known as vertex cover.

CARP calls it node cover.

So node cover is NP hard.

But its cousin, and CARP
mentions this, is in P. So

node cover is problem number
five, is in NP, so NP hard.

Which of them is in P?

I think we said it before.

Let's see if anyone remembers.

Vertex or node cover is number five.

Problem number five is NP hard.

Which of them is in P?

R cover.

Good.

Excellent.

And CARP mentions that.

Edge cover, R cover.

Correct.

As long as we mention
chromatic number above,

there is a version of
chromatic number that's in P.

Does anyone know which version of
chromatic number is actually in P?

There are a few.

But we mentioned one, I think.

Yes.

Correct.

Two.

When K equals two.

When you only have two paints.

And that's also, not surprise Lauren,
called bipartite coloring.

Two groups.

The word bi means two.

Parti.

Parti.

Partition.

Parts.

Two parts.

Two colors.

Correct.

Very good.

That's in P. Correct.

Alright, let's see one or two more.

Zero, one integer programming.

Problem number two.

Zero, one integer programming is NP hard.

Which cousin is in P?

The more impressive problem Karp would not
have known about.

His paper was published too early.

Karp gives a version of a problem.

But give the more impressive problem.

Which problem, or either one's fine.

But which problem is in P?

Number two.

Zero, one integer programming is in NP.

Right.

So that's the one Karp gives.

We gave a little bit fancier one.

A little bit closer to the name.

Zero, one integer programming is in NP.

Is NP hard?

What cousin is in P?

Now Karp could not have known it.

Because it wasn't proven yet.

It was assumed.

But it wasn't proven.

It wasn't proven to 79.

And then a more accessible proof in 84.

If I understand the literature correctly.

What other problem, famous problem,
is in P?

I'll give you a hint.

Danzig came up with the solution.

Although Danzig did not know it was in P.
Right.

So that's related.

Gaussian elimination is another version of
solvability of linear equations.

That's another name.

Unless you meant the other name that I'm
referring to.

But then you have to add a special word.

A fancy word that we use.

So zero, one integer programming is NP
hard.

But what's in P?

Okay.

That's fine.

Linear programming.

Zero, one integer programming.

Programming is a fancy word to mean
solving a system of equations.

So zero, that's possibly what you meant
before.

But the official name is called linear
programming.

So zero, one integer programming.

Problem number two is NP hard.

Linear programming.

Karmakar and Bouchian proved in 79 and 84
that, in fact, it's NP.

They always knew it because, as I said,
Dantzig's algorithm, simplex algorithm,

was always working too fast.

And they just didn't know why.

Anyway, it was proven.

All right.

So that's the... Good.

I think we had a good review.

I mean, there are other questions.

All right.

You know what?

Do we have a minute?

Let's see here.

It doesn't say.

Usually it gives me a time.

All right.

I think we have a... Oh, yes.

Now the timer's started.

Okay, good.

I'm going to talk a little bit more.

Just one last thing, just for completion's
sake.

But in case you did not have a chance to
type present, please do so.

And then I will put these notes
cleaned up, hopefully, and add

some things that we talked
about recently into a set of notes.

And I'll email you those notes later.

So again, if you could, if you haven't had
a chance, say present.

And I'm going to talk a few
more moments, just because

we had a little bit of a
glitch in the beginning.

And I just want to do one more part,
which I think will be useful to you.

And that is in page 96, CARP's paper,
what is called reduction.

Right?

So satisfiability was the first known
problem.

And that was Cook.

And that was published in 1971 to be MP
Hart.

And all problems reduced to
satisfiability.

Which is why Cook considers reduction in
one direction.

Because that's all he was interested in.

Reducing to one problem, which he
identifies as satisfiability.

And we'll prove that,
we'll do his paper in

one sitting later at the
end of the semester.

Which is coming rapidly to us.

Because spring break and then you're
there, May.

Anyway, after we come back from the break,
you have your quiz.

And then we're going to discuss,
begin to discuss the final, etc.

But let's not worry about that now.

So let's pick a random problem.

Let's pick node cover number five.

So the parent is known.

And how to remember
that is the fact that Cook

already, number one, was
known before CARP started.

So in node cover, the parent is known.

But below it, set covering is not yet
known.

And you want to reduce node cover number
five to set covering number six,

which CARP does.

How do you do it?

So set covering has to solve node cover's
problem.

The parent is known.

The child is unknown.

The child solves the parent's problem.

Okay?

And it has to do it in a reasonable amount
of time.

For us, that is P. All right?

And then you would say node cover reduces
to set covering.

And you would say that set covering is
reduced from the parent node cover.

Okay?

And that's the terminology.

We have that in the notes.

I don't know if I used that example.

But please keep in mind the directions,
who's known and who's unknown.

And then CARP, because of the fact that
he's proving the other direction.

Right?

He's reducing away from satisfiability.

Whereas Cook reduces to satisfiability.

CARP then makes the definition that
reductionist is between the two problems.

But he doesn't have to show
one of the directions, because

Cook's theorem already
covers one of the directions.

And the rest he covers.

And then you have Levin, who concentrates
on the cost of doing business.

Right?

How do you translate the one problem into
the other problem?

The output of one problem.

You say the child solves the parent's
problem.

But how do you translate the information
from one problem to the other?

Right?

Or what piece of information is missing
from those problems to solve your problem?

Right?

What's the cost of obtaining that?

So that cost is what Levin concentrates on
when he deals with reduction.

Right?

What is the cost, not of the actual
process of reducing, but of identifying

what piece of information or the
complexity of that cost.

And that's the complexity of the
reduction.

Sometimes it's called a witness,
a certificate, signature, different names.

Okay.

I think that was a good review.

Really was a good review.

I mean, primitive recursive functions.

Please read.

I gave some mathematical examples.

It shouldn't be too hard.

Anyway, if you have any questions,
feel free to email.

The quiz is the Monday after.

This quiz is the Monday when we return
from spring break.

So you'll have a lot of time to ask me
questions if need be.

Wednesday, again, we don't have lecture
here.

I posted a media for you.

And so you don't have to listen to it
Wednesday.

I think it's a good lecture on recursion.

I hope you'll listen to it.

And I sent you notes.

And a week from today is definitions,
an optional quiz, but it will be a class.

But it won't be virtual.

It'll be a quiz.

And I explained that in the email to you.

Okay?

It's the end of class.

Thank you all.

And we'll be in touch by email.

Bye now.