Good morning, everyone.

If you could text if you're present.

And then I will set up the notes,
display them on the board.

Okay, good.

Let me set up the notes.

Please shut off your microphones.

There.

Okay.

That's not it.

Where is it?

Ah, here we are.

Yeah.

Good.

Okay, it's there.

Okay, thank you.

Again, whoever's here, please just text if
you're present.

All right, let's get started.

So we've been discussing, well,
different aspects of the theory.

But we've been concentrating in our
discussions on Turing's notion of solvability.

And solvability is whether a problem can
or can't be solved using a machine.

We've been avoiding the
discussion of efficiency, complexity,

because that is discussed
in analysis of algorithms.

And, well, that's not the reason we've
been avoiding it.

But we've been avoiding it because Turing
was avoiding it.

It wasn't his concern.

He was concerned about, is it
theoretically possible or not?

He was not concerned
about whether you will be

happy in terms of how
much resources it requires.

So the two major sources of...

Two major categories of resources,
of course, are time and space.

Space being the memory.

Time being the number of clock cycles that
the machine will have to go through in

order to execute the lines of your
program.

In that regard, the issue of solvability,
Turing made a slightly different term.

And he would call it an effective
computation.

It's effective if the computation
concludes.

If the machine halts, stops.

And that Turing made, by definition,
the memory storage as the totality of

input and totality of output of your
algorithm.

The entire memory configuration
at the moment that you run

your program is the input
in Turing's solvability notion.

And whatever's on the tape afterwards is
Turing's notion, meaning the tape in memory.

Whatever remains in
memory afterwards in Turing's

understanding of
solvability is the output.

And it's not relevant what the values are
and how you interpret those values.

And it's not relevant how long it takes.

Complexity, though, is interested in that
situation.

Oh, one more point, which we said,
which is that Turing, for the most part,

marginalized memory.

Because the concern of memory.

By simply saying, I'll
give you, Turing says,

I'll give you as much
memory as you need.

Being the amount of memory, basically
because you have an infinite tape.

You have an infinite storage.

So if you have an
infinite storage, infinite

memory storage, you get as
much memory as you want.

Of course, you cannot use the totality of
the infinite storage.

Because the only way you
could continuously write on

that infinite tape is if
you have an infinite loop.

Which then means that
your machine never halted

and you never got an
effective computation.

Which point to Turing means it wasn't
solvable.

If no such Turing machine could exist,
it will stop.

So the infinite loop is the nemesis of
solvability.

Having said that, we do actually need to
explore the notion of complexity.

Because there's another concept in
computer science, in computer theory,

which was quite significant.

It's a very theoretical concept called
non-determinism.

And in order to understand
non-determinism and its repercussions,

we do actually have to go
into the notion of complexity.

Now, we're not going to do it to the
extent... we're not going to discuss

complexity to the extent that you will learn
it in 323 or 700 analysis of algorithms.

But there are some key
categories that we need to

know and some basic
assumptions that we need to know.

Okay, so that's... so
the two goals of today's

lecture is the role that
complexity does have.

Or to the extent, let's say it that way,
to the extent that complexity has a role

in computer theory, we would like to start
discussing today.

And the other issues specifically leading
up to the notion of non-determinism.

Now, we are going to deal with... here on
line three, I mentioned it.

Okay, yeah, right.

The computer... as I say, it takes a
second for the machine to release the file.

So if I need to edit the notes on the
board, it takes a second.

All right, whatever.

Okay, I'll just continue talking.

And then when it finally releases the
file, I'll be able to... Oh, there we go.

Okay.

What I want to say here is, please,
at last class...

Line three.

Last class, I told you the
name of CARP's paper,

Reducibility Among
Combinatorial Problems.

Please locate and
download the PDF, either to

print out or to your
machine that you're using.

And as well, we're going to need,
although much later in the semester,

but it is the paper that CARP technically
was based on.

The paper by Cooke.

So again, in the notes
at the end of last class,

I wrote what the
names of the articles are.

Please do a search and get a copy of the
paper.

They are available on the web.

And just download them because we're going
to read through them.

Well, the Cooke paper, not as much for a
different reason.

I'll explain it later in the semester.

But the CARP paper, mostly, we're going to
go through.

And even though it's a theory
paper, it has a tremendous

amount of relevance
in practical applications.

So we need to go through it.

Okay?

So please do so.

And that has to do with the famous problem
of what is called P equal NP.

And we will just at least define it
technically, officially today.

All right.

So we mentioned... Okay,
so we mentioned this point.

Now, so on line 13.

So when we talk about complexity, and
we talk about that an algorithm is order N.

Big O of N.

The O was chosen because of order.

Orders of.

Orders of N.

So what does that actually mean?

So we'll... I want to... If
you've learned it in 3.23, fine.

So then we're summarizing some points that
we need to discuss.

If not, well, then here's your first time.

Anyway.

Order of N time.

If you say order of N time.

O of N time.

So that's based on the amount of time to
read in an input of length N.

So that's really important the way I
worded it.

It's really significant.

It does not refer to the value of N.

I know colloquially and innocently,
students always think that the...

That we're dealing with the value of N.

We're not dealing with the value of N.

We're dealing with...

And that's, again, consistent with the way
Turing viewed things.

It's not the value that's stored in
memory.

It's how much memory.

So order of N means that you have...

The algorithm takes a similar amount of
time as to reading in an input of length N.

And again, the way I worded that is
precise.

Very often in...

When you're dealing with analysis of
algorithms, you're applying it to one algorithm.

So you think intuitively that you would...

You assume that the
purpose of the orders of N,

as it were, were to
analyze a specific algorithm.

But that's not true.

In fact, there are some simplifications
that analysis of algorithms makes.

So that you don't actually get the true
model, mathematical model, of how much

time or how much space, as the case may
be, for a given algorithm.

Rather, we're looking at categories.

Categories of functions.

And in that context, what
you're really doing is comparing

algorithms to each other in
terms of how much time they take.

And now you don't want, for the reasons in
the analysis of algorithms, and a little

bit based on the theory, Turing's theory,
you don't want that...

You have your implementation of heap
sorts.

I have my implementation of heap sorts.

One of them is slightly different.

You know, it's a slightly different amount
of time.

Overall, we want to say we both have the
same algorithm.

And we'll say they're in N log N, as the
case, you know, if you remember heap sort.

It's not relevant right now if you know
what heap sort is.

But the point is, it's an algorithm for
sorting.

It's one of the faster algorithms.

And it's N log N, right?

So yours is N log N plus N.

And mine is N log N minus 5.

And N is maybe more expensive.

They're not interested in that.

The gestalt, the overall
impression of what the

algorithm gives you
and exhibits is N log N.

So your version and my version,
or whatever implementation you're doing,

we're going to say they are of the same
category.

They are of the same order.

So order is really about comparing.

It's about getting categories
of complexity, not as

much trying to analyze
specifically one algorithm.

Anyway, so a key line here, again,
on line 13, is that we're not referring to

the value of N when we say that the
complexity of your algorithm is order N.

We're trying to say that the N actually is
a length.

N bits, the amount of time it takes to
process N bits.

That amount of time is the time that your
algorithm takes, a linear search,

going through the elements of the array
one by one, for example.

Okay.

Now that's quite important because the
difference in numerical value between the

value of N and the amount of memory that
is stored, and the amount of memory you

need to store the value that you thought
it was, is actually, there's an

exponential difference or inversely log,
depending who you're comparing to whom.

And the reason is that N will always be
less than or equal to 2 to the K,

where K is an integer, the lowest such
integer.

There is some lowest, smallest integer K,
such that N, an integer, random integer N,

is less than or equal to 2 to the power of
K.

But then, this means that
K is the number of bits to

store the value N, since K
is going to be log base 2 of N.

Right?

And that would mean log base 2 of N is
equivalent to the number of bits you need.

So it comes out that
N equals... Right?

So N basically is 2 to the power of K.

So the issue of value is N.

The issue of length of memory is K.

What's its relationship?

So N is exponentially more than K.

K is the log of N.

So the relationship between value and
length of memory is exponential,

a logarithmic depending on which direction
you're going.

Right?

That's a big difference.

Okay?

That's quite significant.

And it's... Well, you
know, it's anachronistic.

Meaning, what I'm about
to say is technically a time,

a historical error in
that it didn't happen first.

But this would give an explanation to Jack
Edmund's distinction that we're going to

say at the end of the notes here,
which is that a notion of complexity

should be differentiated
between whether it takes a

polynomial amount of time or
an exponential amount of time.

Now, this would give a very solid theory
basis for that assumption.

I say it's anachronistic because that's
not the reason why Jack Edmund said that.

But the fact is that right now,
when we have this understanding,

it's a very good reason to differentiate
exponential versus polynomial.

And that the exponential is that much
more.

It's that much more complex.

So anyway, that's the distinction between
the value of n versus the length of the

number of bits you need to store that
value.

So that's order of n.

When we say that n, n is really the number
of bits to store.

Not the value.

Now, just for notational purposes,
I guess I could put it above in the notes.

Where could I put it?

When we talked about infinite loop
halting, I guess we could put this here.

All right, you know, okay, fine.

I'll leave it where it is.

Just so you should...

In Davis's book, he introduces a notation
up arrow and down arrow.

And down arrow means that the code
implementing the function f of x down

arrow, the arrow pointing down,
means that the code halted.

That it stopped.

That the computation was effective using
Turing's terminology.

F of x up arrow, up arrow means it went
through an infinite loop.

Okay?

We're not... We may once in a while
use that notation, but generally not.

Anyway, but in Davis's book, he has it.

So that's something you should know.

Okay.

Now, a bunch of terminology, a little bit
more.

And then we'll talk about the algorithmic
categories.

So terminology related to what we just
said.

If code exists, okay?

If you have code and that code could
compile.

We're not saying what it does.

We're not saying whether it's good code or
bad code.

Meaning does it go through an infinite
loop or not?

If code exists, then the function that the
code implements, whatever it does, right?

Whether it does it correctly or not,
is called partially computable.

And that is also known as recursively
enumerable.

So there's that big word recursion.

And I mentioned on the first day,
very briefly, that a name for this field,

for the field of computer theory,
is called recursion theory.

So that's obviously a big word in the
context of our course.

The thing is, though, that the word
recursion used by the theorists in this

context, recursively enumerable,
isn't what we think of recursion.

But still, it was part
of, but there is a

relationship, but it's
not really what we think.

It's a different aspect, and we will
hopefully get to it.

But it is true that an important aspect,
which is going to permeate throughout the

semester, is we're going to look at
different models of recursion.

And Davis does that in his book.

So an important name that was given to the
complexity, computability and complexity

theory of computation, or computer theory,
is recursion theory.

Okay, anyway, so one more time.

If code exists, if you could write any
code, if you randomly write code and it

compiles without errors, it doesn't mean
that it's going to run.

If you shut off the microphone.

It doesn't mean that it will run,
but if code exists, then the function that

the code implements is called partially
computable.

Okay?

So that's a key term here.

It's also known as... I'm going to just
make it bolded.

It's a key term.

Also known as recursively enumerable,
which is also a key term.

Anyway, note, and this is what I was
saying before.

This function could be a partial function.

You know, it's partial in the sense of
mathematics.

That is, we do... meaning without output.

That is, we do not require that the code
halts.

At this point, we're not... we do not care
if the code actually halts.

We just care does the code exist.

Okay?

So we're going to make
that distinction, and then

we're going to add a
level where it does hold.

But right now, we're starting very simple.

If you have code and it compiles,
and there are no contradictions,

there are no errors, so
then that code... meaning

that... whatever it does is
called partially computable.

Right?

So it is possible that on any given input,
your code may not hold.

Okay?

All right.

And so, in fact, it could
be a partial function where

the program goes through
an infinite loop, right?

Where the function is not defined.

Okay, fine.

That's... I was going
to say something.

In fact, it could be a
partial function where the

program goes through an
infinite loop for every input.

That's what I wanted to say.

All right?

In other words, it's still partial...

If you could write code,
and no matter what it

does, it's still called
partially computable.

All right?

If, in addition, the code is well defined
for all inputs, that is that there are no

infinite loops, and every input has an
output.

So the other extreme,
there are no infinite loops

in your code that you
compile, that you're running.

And for every possible input, then the
function is a total function.

It's well defined.

And the code is called computable.

Okay?

Now, so...

And we just said that another name for the
computability theory is recursion theory.

So partially computable was called
recursively enumerable.

So there's that name that I mentioned a
second ago.

Shorthand, very popular in the theory
field.

If you see RE, R dot E dot, that means
recursively enumerable.

So it's partially computable.

There is no claim as to whether it will
hold or not.

And computable is called recursive.

So it's a spin-off.

If it's actually total, then we will say
it's recursive.

Right?

And then, as I mentioned, again,
as I mentioned here on line 27,

although this has nothing to do with what
a programmer calls recursion.

Not really.

Anyway, we'll get to what it means a
different time.

But we're going to
spend a lot of time this

semester analyzing
the notions of recursion.

All right.

So now let's get to the topics issues.

That's some of the definitions we need to
know because we're going to use them.

All right.

All right.

And that's more in terms of whether a
machine halts or not.

And that's what we've discussed in the
past.

All right.

Now, so there are a number of categories
which are important for us to discuss that

will lead up to what we're going to spend
a few weeks on, which is understanding and

reading hopefully through the entire or
the major part of Richard Karp's paper.

So again, please bring it with you.

Okay.

Make sure you have either printed or
downloaded Richard Karp's paper and the

information for that paper I gave in the
last set of notes.

All right.

One distinction that's made, which in
mathematics and numerical analysis and

advanced applied mathematics, which is
critical for understanding our discussion

and for Karp's paper, is a decision
problem versus an optimization problem.

Decision problems have a Boolean output
deciding whether or not a certain property

or relationship holds true under the given
input.

Okay.

You have to decide yes or no.

But that doesn't necessarily mean that
you've got the output.

It just means that we will tell you
whether a condition holds true or not.

In other words, that is the output.

It's not a necessarily... You could give a
numerical value that solved your problem.

But technically decision problems are
whether it's solvable or not.

Whether you... Or... Well, that's too
strong because that's Turing's language.

At this level, we're in the analysis of
algorithms.

So decision problems are whether a
property exists or not in the input set.

Optimization problems
do have a numerical output

representing the best
value that can be obtained.

And how to obtain it.

Relative to the given problem.

And, of course, the given input.

Now, these could be either maximum or
minimum.

Just... Best value isn't
always the maximum value.

So it could be also the
minimum value, max

or min, of a function
over a range of inputs.

All right.

Decision problems generally have a
verification procedure.

And that's an important point that CARP is
going to need.

Decision problems generally have a
verification procedure that the user can

check after the program provides the
decision based on the inputs.

However, regarding optimization
problems, how can we check

whether or not the proposed
maximum is truly the maximum?

Let's assume your optimization problem is
to find the maximum, right?

Over...

Of a given function over a certain range
of values.

Okay.

And then your program figures out what the
maximum is.

Well, very nice.

But I would like you to prove to me,
show it to me, that it is.

Okay.

Well, how are you going to do that?

That's tricky.

How are you going to...
How are you going to...

You know, if we're regarding
optimization problems, how are

you going to prove to me that
what you have is truly the best?

Maybe there's one other number.

Now, in calculus,
there is a derivative test

to test for optimal
points of a function.

Is the first derivative
of that function, f

of x, the derivative
of f of x equal to zero?

If the derivative is equal to zero, if
the derivative of the suggested point.

..

If you suggest point x is a maximum or a
minimal, an optimal point...

I realize the spelling really is bad.

Hold on.

Derivative.

Let me spell that correctly.

Okay.

That's better.

So, the point is that then f of x will be
zero if it's an optimal point.

But this is a necessary condition,
but not necessarily sufficient.

Meaning, you could be tricked.

It must be the case that if
you have an optimal point, then

the first derivative of the
function at that point is zero.

But just because you found a point that
has the first derivative of zero does not

actually mean, does not guarantee that
it's an optimal point.

Now, so why?

So, first of all, just
because you're an optimal

point, line 41, it's
either a min or a max.

The first derivative test does not tell
you whether it's a min or a max.

It just says it's an extreme point.

An extreme point in the function.

Okay.

But more importantly for what we're saying
now, there's a curious situation called a

saddle point that
has the first derivative

equal to zero, but it's
neither a min or a max.

I'll give you a link to a picture,
a mathematical drawing of this,

what's sometimes called the saddle
function.

It looks like a saddle on the cowboys,
cowboys, cowgirls use on the horse.

All right.

In that example, the function is x squared
minus y squared.

Okay.

And they're called hyperbolic paraboloids
because the curve is hyperbolic concave,

right?

So that means that the highest,
it's an upside down u.

So the highest point is going to be a
maximum, but it's only in one direction

because it's a two dimensional function in
x and y.

So in one direction, it's a concave.

In a y direction, it's concave.

But in the other direction, it's
parabolic, convex.

And convex is like the letter u.

So the bottom is a minimum.

So the point is that, and these two points
are the same point.

So the fact is that you've got a point in
the middle.

And depending on your perspective, from
one direction, it looks like a maximum.

And from the other direction, it looks
like a minimum.

But the fact is it's neither.

Well, the fact is that it's neither.

Right, okay, fine.

Good.

Now, so therefore, there is actually a
further test, which is the second derivative.

If you take the second derivative,
so the first derivative of your function f

of x, if you assume x is an optimal point,
either a max or a min, so then the f of x

must be, the first derivative must, f prime
of x, the first derivative must be zero.

But you're afraid that it's a saddle
point, that it's a trick point.

So you test the second derivative.

And then the second derivative,
if it's zero, so that's a saddle point.

And if it's plus or
minus, that will actually

determine whether a plus
will be a maximum point.

And if it's a saddle, it will be zero,
the second derivative, at that point.

And if it's negative, then the second
derivative, then it's a minimum point.

Okay.

But that's from a mathematical point of
view.

From a computer theory perspective,
even that is not sufficient.

Okay?

Now, if you want an approximation,
then you may be happy.

But if you're actually looking for the
true, true answer, we're not done yet.

Not in computer theory.

Why?

So this leads us to our next category.

Global versus local.

So, take a look at cell D... let's consider
cell D57, which looks like a maximum.

It seems to be the highest point nearby.

And let's look at cell E61, where it looks
like it's the lowest point locally.

Right?

Nearby, it doesn't look like anyone's lower
than the value, the function value at DE61.

The fact is, neither are the true
solutions.

Because if we consider
cell F53, the Y value is

higher, and the function
gives a much higher value.

That's the global max, meaning over the
entire function, nobody... the function

does not achieve a higher value than it's
achieved at point X4, the highest point.

And likewise, perhaps, in cell G64,
in cell G64, that's the global min.

Right?

Nobody has a lower value.

Now, I point out, also, that min was
achieved, for example, in B64.

From... it is possible...

I point that out, because it is possible
that more than one point has the same value.

It doesn't have to be unique.

Anyway, so the difference between local
and global.

So the calculus test only will show you...
first derivative, second derivative...

will only show and confirm that your
point...

that your program has concluded as the
solution to the problem is a local optimal.

But if you want the true solution, and
local may be good enough for what you want.

It may be a reasonable, but it's... but
you don't know 100% whether it's the best.

So from your point of view, it's a... it's
a very strong, approximate solution.

The fact is, it could very well be that
elsewhere that your program did not find

is a... is a better maximum or a better
minimum, and those are the global.

Not just better than what you have,
but if it's the best over all

possibilities, over all inputs for the
function, then that's the global max or min.

So in computer science, how can we verify
an optimal global solution...

versus an approximate local solution?

So this typically boils down to a time
resource.

There is this old-fashioned approach
called the exhaustive search.

Exhaustive search.

Basically, what you would do if you didn't
know anything else, which is...

Exhaustive search is also known as brute
force.

That actually is an official name.

Both are acceptable names, exhaustive
search as well as brute force.

Anyway, basically, simply...

But it's easier to describe than to...

It's costly to implement.

But simply test every number in your input
range.

If you want to know whether your program
gave you the true best, we'll try every

input and see, test rather, you know,
and compare.

And do you find a different number that
gets you a better output, a better,

higher value?

Right?

So the...

It is solvable, but highly complex in that
it will require a large amount of time.

Okay?

So this begs the question, how to
objectively differentiate...

Okay, so... Well, it
begs on two questions.

One of which I will answer later,
which I... Maybe I could put here.

I put down...

So CARP... Maybe
I... You know what?

Let me put that now.

Give me one second.

It may be... Maybe it'd
be better to say it here.

Well, okay.

So I have it later.

Give me one second.

I mentioned it later.

Okay.

Maybe I should mention it both times.

I'll get the right sentence for you.

Okay.

Here.

Give me one second.

I'm just... I'm breaking this
up so that way I could copy it.

So I'm going to put it in two places
because it really belongs in two places.

Let me move this up.

Let me write this one second.

Where are we?

Yes.

Okay.

Here.

Okay.

So CARP handles this situation.

Handles this issue.

What's the issue?

The issue is that you would like to
verify...

I'm going to put in parentheses.

Right?

Verification.

You would like to be able to verify that
the algorithm got the right answer.

Yeah, we trust the computer that it did
what we asked it to do.

But do we trust ourselves that we told the
computer what we should tell it?

You know, did we get it right?

So you want the ability to verify.

Now in the case of decisions, so then
that's sort of a built-in...

Assuming you didn't
have an error in logic, then

the solution, the
output is the verification.

Right?

Can you decide?

But in the case of
optimization, how are you going

to be able to prove you
got the correct answer?

Now, Karp deals with...
Now, he doesn't handle it.

He doesn't solve the problem.

He deals with it.

He has to deal with this issue, and we'll
explain why when we start Karp's paper.

This is how Karp deals with it.

Karp deals in his paper.

Deals with this verification issue by
transforming the underlying optimization

problem into a meaningful decision problem
by introducing a new threshold K and

simply asking, will the
solution obtained be greater

or equal or less than
or equal to K as needed?

Thus, the optimization problem is now a
decision problem relative to new parameter K.

So, that's a little bit of a way out.

I know it's a way out, but not yet.

Again, I'm not here blaming Karp.

Karp was not trying to solve the issue
completely.

The issue is that if you have...

Imagine we have... and we're going to
mention, I think, a little later.

Let's imagine you had a random algorithm.

Okay?

And such algorithms exist.

Not too popular, but they do exist.

And a random algorithm based on random
number generation tries to hopefully

intelligently guess a solution to your
problem.

Let's imagine you had a
random algorithm that's going to

try to guess which input gets
you the largest output, right?

Optimization.

Okay?

So, how are we going to verify that?

Now, especially if it's random,
right?

You're not going to really trust a random
algorithm that's going to say to you,

well, this gets you the most profit,
right?

You're not going to invest unless you had
a more solid basis for that result, right?

A random algorithm got you an optimization
value.

And now, you're wanting to invest.

It says that do this, you know,
this portfolio by 25%, you know,

technology stocks, 25%, 5% food stocks,
vehicles, I don't know, whatever it does,

right?

And your algorithm says this is the best.

Well, you want to invest your money.

So, you're not going to do that unless
it's a little stronger.

Unless the information you get is
stronger.

So, that's what CARP did.

CARP said, well, not necessarily are we
going to solve the global issue,

but we can make the local issue into a
stronger result.

If you could transform the underlying
optimization problem into a question of,

you know, can, will the output be greater
or equal to a certain value?

Because that value is the value we really
need.

In other words, I won't invest unless my
profit margin is the following.

So, greater or equal.

So, the computer shows that it can be
achieved.

Okay?

Now, does that mean that
the value that it suggests

or the inputs that it
suggests is the true global?

No.

It may not be the best output,
but it's, for me, it satisfies my need.

So, therefore, it's an excellent
approximation algorithm, but it's not

going to be necessarily, does not
guarantee you the true optimization point.

Anyway, CARP, for another reason also,
which is when we do CARP's paper,

CARP is going to transform optimization
problems into decision problems in order

that we can decide this in a reasonable
amount of time.

So, this is done by CARP so that a
verification procedure of an underlying

optimization problem can be achieved in a
reasonable amount of time.

That's the actual reason that CARP does
this.

But, you know what?

Actually, I should put that below.

Right?

Because that is the extra statement that
we need here when we talk about it.

Let me put this below.

We don't need that now.

All right.

Anyway, so that...
It's an important point.

The issue of the category...
Let's get back to the categories.

So, the categories are decision
versus... Global versus local.

Well, okay.

Decision versus optimization and global
versus local.

All right?

Did we... Actually,
no, we didn't.

Okay.

Good.

All right.

Now, it comes along Jack Edmonds.

All right.

So, here.

So, this begs the question, line 79 here.

This begs the question, how to objectively
differentiate between a reasonable amount

of time versus an unreasonable amount of
time.

Right?

Right?

The point being, you could verify your
solution, guaranteed, by trying the

exhaustive search, by trying every
possible value.

That very often is extremely unreasonable.

Right?

So, we need to understand a threshold of
what makes the amount of time reasonable.

Okay?

So...

And that reason... The notion of reasonability
in this context is called complexity.

The person who set the heuristic was Jack
Edmonds, a friend of CART.

He was trying to explain why Danzig's
simplex algorithm for solving linear

programming problems
always seemed to find

the solution in a
reasonable amount of time.

Danzig gave us...

So, the question is to
solve a linear programming

problem, which I'll define
right here, lines 81, 82.

Danzig wanted to solve linear programming
problems.

He gives a solution called the simplex
algorithm, which I'll summarize in a second.

Linear programming problems solve a system
of linear equations, which is the

summation of weighted linear variables,
not raised higher than degree one.

That's what makes it linear.

A linear variable means
you didn't raise the variable

to a power, so you didn't
do x squared, for example.

And then you subject it
to numerical constraints

on the variables,
bounds on the variables.

A key feature of the simplex algorithm is
that the constraints effectively enclose

the search space of values by a convex
polyhedron.

And the simplex algorithm will be jumping
from endpoint to endpoint in this

geometric polyhedron, and then makes an
intelligent decision as when to jump off

the endpoint, the corner points,
to obtain the true solution values.

Edmund conjectures that the
number of endpoints searched

by the algorithm is only a
polynomial number of endpoints.

But if the number of
endpoints were exponential,

then that would take an
unreasonable amount of time.

So Edmunds is the one, based on this
situation, of analyzing the simplex algorithm.

Edmunds was a mathematician.

He was a graph theory mathematician,
and he was interested in geometric graphs,

such as this polyhedron that bounds your
search space.

But he was not a computer scientist.

So this distinction between polynomial
versus exponential was accepted by CARP.

And that's what popularized it.

From that point on, and it's really sad,
in many, many computer science books,

they mention CARP as distinguishing
between polynomial and exponential.

And he is the first
computer scientist to publish

that, but he's not the
person who suggested it.

It was Jack Edmunds who suggested it,
a friend of his.

Now, anyway, so in his paper on p equal
mp, he makes this distinction.

The algorithmic perspective
of the paper we're going to do,

and hopefully you will either
print or download to your device.

The algorithmic perspective
of this is that polynomial

time is essentially a fixed
number of nested for loops.

Whereas exponential
amount of time is an exhaustive

search, trying every
possible combination.

So that's, in essence, what's going on.

Why do you have polynomial-timed
algorithms?

Because, really, it's equivalent to... you
expect a for-loop within another for-loop.

The for-loop is i equal 1 to n.

You put it into another for-loop,
so that's n of n, n squared.

You put it into another for-loop,
it's n of n of n, n cubed.

Basically, you're iterating through
for-loops.

That's polynomial.

But, exhaustive search has to go through
every possible situation.

And when you deal with possible
combinations and possible sequences,

that's usually exponential.

So, Edmonds made the
suggestion, CARP accepted it,

that polynomial is a
reasonable amount of time.

Exponential is not a reasonable amount of
time.

And we will spend a lot of time on that
when we discuss CARP's paper.

And that will lead into
the p equal mp problem,

which I would like to
discuss with you now.

Because that will lead, you know, shortly
into one more very important distinction.

And, which is deterministic versus
non-deterministic algorithms.

That's another category.

Mathematicians do not have this.

We do.

Now, they probably discuss it now also.

But you won't typically hear this in your
courses.

Okay?

Anyway.

Sorry.

Okay, good.

Make sure that the
computer... Okay, good.

Yeah.

Just wanted to check the screen.

All right.

So, deterministic versus
non-deterministic.

So, that's what we're going to embark in
right now.

So, first of all, let's remind ourselves.

A total function maps an input set to an
output set such that every input has an

output, as opposed to
a partial function, which

admits, which allows for
some undefined inputs.

And we'll discuss that later, a different
time.

Every input...

Every input has no more than one output.

That's important.

Colloquially, in calculus textbooks,
this used to be called the pencil rule.

What you do is your x-axis is horizontal.

Your y-axis is vertical, up and down.

Your x-axis is left to right.

You draw a function on that graph paper.

And you take a pencil standing up in
vertical position.

And you move it along.

And if the pencil hits
more than one point on your

quote-unquote function, it's
not mathematically a function.

If you're...

As you shift that vertical pencil,
that infinitely small pencil, thin pencil,

from left to right, and so then...

And it only hits the drawing of your
function, the outputs of your function

only once, then that is mathematically a
function.

Okay.

That's the backdrop.

Computer theory calls such algorithms.

Okay?

Deterministic.

So, what's called a total function in
mathematics.

Now, again, line 99.

Every input has an output.

Line 100.

Every input has no more than one output.

Now, let's say an algorithm
algorithmically.

So, we call your code that does similarly
deterministic.

A versus one.

Paralleling one.

The program or algorithm halts for every
input under consideration.

So, on line 99, right?

Cross-reference line 99 above.

Right?

So, that's our version.

Computer science version.

And then, of course, reference line 100
above.

So, every input has an output.

We say that every input, the program or
algorithm halts.

Number 100 said every input has no more
than one output.

So, then we say, given on line 104,
given any step of the algorithm is

well-defined, i.e., only one choice,
what step to conduct, what line,

what command to conduct next, based on the
current values of the variables.

Okay?

Now, Stephen Cook
elaborates, he introduces

and elaborates the
notion of non-deterministic.

Condition A still holds true.

Namely, that there will be an output for
every set of inputs.

Okay?

Every input has an output.

That still holds true.

Okay?

But, the asterisk I keep talking about is
that what we've been, and we've repeated

this earlier, subject to GEIGO,
an acronym for garbage in, garbage out.

What we mean is, when we
are, it's not theory's concern

whether your code does
what you wanted it to do.

It's not theory's concern, not for this
semester.

It's not theory's concern whether you got
it right when you wrote the code.

It's only theory's concern that you did
not have a contradiction.

You did not have a compiler error.

Right?

And now, we're adding
that, in fact, your code doesn't

go through an infinite loop
at any point, for any input.

Okay?

But, it's not theory's
concern that your output, that

your algorithm generates is
the solution to your problem.

It's only that it didn't make a mistake.

It followed the instructions.

That notion is called garbaging,
is an aspect of garbage in, garbage out.

If you make an error, don't
blame the machine or the

algorithm, don't blame the
computer for the output you receive.

All right, but the second condition,
namely that every input has no more than

one output, which is required for a total
function, so Cook relaxes it.

Cook relaxes that under non-determinism,
in that, and this is a theoretical

concept, the programmer, at a point in the
code, could rely on the computer to

correctly decide which
step to take, instead of

figuring out the next
step or decision to take.

Okay?

What we're saying is that, theoretically,
your non-deterministic code for any step

of your algorithm could have more than one
possible pathways.

And not based on... this is important.

If you have a switch, a case statement,
if-then-else, cascading if-then-else,

we could also have multiple pathways,
which will be the next step.

That's not what we're talking about.

We're saying that we tell the computer,
the programmer tells the computer,

well, I know it should... the answer
should be one of three possibilities,

or one of three pathways.

I don't know which one it is, so computer,
choose it for me.

And we'll formalize that in a moment.

But the key here also is to understand
that it's not random.

You know, you would think that this
statement is random.

You could have a random algorithm doing
that.

But that's not non-determinism.

Okay?

So, in a... so, let's maybe make that
point.

That's a very important point.

Note.

Note.

This non-deterministic process does not...
does not... or is not.

Okay.

Okay.

This non-deterministic... process is a
little too strong.

Give me one second.

Let me think of a better word.

This non-deterministic procedure.

A little bit less strong.

This non-deterministic procedure does...
is not implemented...

by a switch... or a case statement...
or... which is similar.

Different languages.

Some have switches.

Some have cases.

Slightly different.

But basically the same.

Switch case or if... or nested
if-then-elses.

Nested or really...
In fact, it's not nested.

It's called cascading... if-then-elses.

Right?

That's not what we're assuming.

This non-deterministic procedure is not
implemented...

by a switch, a case, or cascading
if-then-else... nor is it implemented...

by a random decision...

of which pathway or value to take.

All right?

So that's not the case.

All right?

What is the case?

So it's a wild theoretical concept.

Instead, non-determinism...

assumes...

that the intelligence of the machine...

can instantaneously... and we'll...
we'll talk more about that in a second...

can instantaneously...

make... this...

decision...

and correctly.

Okay?

We'll... we'll get back to that.

In a similar manner as above, non-determinism
can be simulated deterministically.

Because in a worst-case scenario,
the program can try all possible choices,

and whichever leads to a successful,
effective computation will be...

will be the chosen path.

Right?

You could... you know...
it's... to... to... it's... well... it's...

it's a little bit more than that,
because it actually makes a...

it's not just successful and effective
computation...

to obtain the true solution.

It's a little bit more, because it's not
that just simply...

it'll figure out how to halt.

It's that... when it halts, it
will get the correct output.

So...

Turing knew this.

Turing knew this.

That... non-determinism
is a luxury.

It's not... it's not
a new... well...

it's a new concept, but it's not something
that cannot be achieved, or something that

you must have, in order to obtain a higher
level of computation.

not from the... the
theory point of view.

Not from a solvability point of view.

Okay... well...

okay... from a
solvability point of view...

any non-deterministic machine or
program...

can solve...

only... that which...

which... the deterministic
machines can solve.

Okay... that's... it's...
okay... that's very important.

It is only an issue... it... the relevance
of the non-deterministic... okay...

therefore... the relevance of the
non-deterministic concept... in computer science...

is going to mainly boil down to time
considerations.

How much time does it take for your program...
or the computer to make the decision?

Now...

incorporating Edmund's heuristic...

if the decision only takes a polynomial
amount of time... it is reasonable.

If it takes an exponential amount of
time...

which is typically the situation...
if it... shut off the microphone...

I believe the lure... yes... shut off
your microphone... you think it would...

if... turn off you microphone...

whoever's talking... shut off your
microphone... about the whole...

this is like a second twenty
something... maybe christmas...

Hello... stop talking...

okay... I think I was able
to mute them... All right.

How much time does it take for your program
or the computer to make the decision?

Now, so, right.

If it is an exponential amount of time,
which is typically the situation for

exhaustive searches, then it's an
unreasonable amount of time, but is salvable.

It's unreasonable.

It's complex, but it is salvable.

Well, we shouldn't say that.

Okay.

Hard.

Okay.

Well, we'll... Because there's a
technical definition of this word.

We'll just say complex.

There you go.

All right.

Following this, the P, in
CARP's famous acronym P

equal MP, the P stands for
polynomial amount of time.

All right.

Polynomial amount of time.

Because CARP was only interested in a
reasonable amount of time.

He was only considering algorithms that
take a reasonable amount of time.

We're going to talk more, again,
what P equal MP means.

Okay.

Now, as I mentioned before, there is
another, one other approach for the

situation that the program relies on to
the computer to make a decision.

And that's called a random or
probabilistic algorithm or programming.

Let the computer make an intelligent
guess.

But this does not necessarily guarantee
the best solution.

It may only achieve an approximate
solution.

So, for example, a course that I sometimes
teach, when they give me the ability to do

so, when the college has enough funding to
support lots of electives.

Anyway, for example, genetic algorithms
employs random number generators and

likewise cannot guarantee a perfect
solution.

But only an approximate solution.

Approaches that provide approximate
solutions are sometimes called heuristics.

One specific heuristic
that deserves mention,

we should mention, is
the greedy approach.

Which states that when a
decision should be made,

whichever choice offers the
most value right now is chosen.

Without considering what this choice will
cause in the future.

That is an immature approach.

Imagine a child in a candy store.

Right now, that child wants to eat as much
chocolate as possible.

As much candy as possible.

Let's see.

No, you don't like chocolate.

As much candy as possible.

Right?

And if it has, you know, the money that it
made from shoveling.

Right?

And it's just buying up candy and eating
up candy.

The child thinks that's a great decision.

When the child goes home, Mommy,
Daddy, I have a stomach ache.

Right?

Bad decision.

But a child is not capable of thinking for
the future.

The child can only see what's now.

It's not yet mature
enough to make decisions

now considering what
will happen in the future.

Greedy does that.

Greedy makes the decision what happens
right now.

Without considering what will happen in
the future.

The importance for mentioning this.

Is that when students learn this approach.

Greedy.

In analysis of algorithms.

And it's an entire chapter.

In the analysis of algorithms books.

So students think.

That it will always work.

And obtain the perfect solution.

When a fact is not guaranteed.

The reason that the students think this.

They have this impression.

Is that textbooks collect the cases.

Where greedy actually gets the correct
solution.

And presents only those.

Right?

The analysis of algorithms books tend to
give you.

These situations where greedy worked.

So sometimes students walk away thinking.

Oh, greedy is a valid.

There is a valid way of obtaining.

Of guaranteeing you.

Obtain the correct solution.

When in fact.

That's not guaranteed at all.

There are some cases, sure.

There are some cases where random
algorithms.

Get you the correct solution.

And you could prove that.

There are some cases where greedy.

Gets the correct solution.

You can prove it.

But you can't assume that as a rule.

Cool.

All right, so now terminology.

Regarding any complexity
class C, and there are

thousands of complexity
classes, we know only a few.

N, that's linear, that's complexity class,
and squared, we know a bunch.

But in general, if you have
a complexity class, order of,

whatever that order of is,
that's its own complexity class.

So regarding that complexity class C,
a problem is considered C hard if that

problem is as hard, but could be harder,
than any other problem in C.

So if I have a new problem and I want to
categorize it, and I'm concentrating on a

certain complexity class, I could say it's
hard for that complexity class if you

could prove that the complexity of your
algorithm, of your problem, is at least as

hard as any problem or the complexity of C
itself.

Now, the C hard problem is called C
complete, if in addition to being C hard,

one could verify the solution obtained
within the complexity time C.

Right?

That's pulling back what we said before.

Verification.

For the Karp paper, the complexity class
is the set of all polynomial timed

algorithms, which he calls P. That's the
complexity class.

So RC is going to be called P. Considering
what is mentioned above, Karp wanted to

deal with complete problems whose
verification is relatively easy.

Yet a number of interesting
problems that Karp considers

at their core are really
optimization problems.

So as we mentioned above, Karp as
mentioned above, and I'm purposely doing

it twice, because the context is slightly
different, but both times important.

As mentioned above, Karp handles that by
transforming the underlying optimization

problem into a meaningful decision
problem, by introducing a new threshold,

K, and simply asking, will
the solution obtained be,

will it be greater or equal
or less than or equal to K?

Thus, the optimization
problem is now a decision

problem relative to
the new parameter, K.

Alright?

This is done so that a verification
procedure of an underlying optimization

problem can be achieved in a reasonable
amount of time.

Okay?

Well, when we do the Karp paper,
we will notice that a lot.

Okay, good.

So that is the P part.

Now the N part.

So P equals NP.

The P on both sides means polynomial-timed
algorithms.

Well, wherever P equals NP.

We mentioned it.

We'll mention it a number of times.

But now the N.

So P equals NP.

The N refers to non-determinism.

So let's talk a little bit about that.

Let us explore.

Let me just make sure the board has it
properly.

I'm sorry.

Here it is.

Yeah.

Okay, good.

When I switch tabs, I just want to make
sure it's on the board.

Alright.

Let us explore the definition of
non-deterministic.

So deterministic.

Let me just take a quick drink in my
throat.

Okay, thank you.

Deterministic algorithms are such that
given any instruction or command that the

CPU is about to execute, the machine is
about to execute, the decision as to which

instruction to execute is completely
determined by design.

The program tells you ahead of time what
decision to make based on the values of

the variables stored in memory up to that
point and at that point of execution.

Right?

So that is the computer science version of
a total function.

As mentioned in the
previous tab, this is the

computer science
version of a total function.

Well, we've got to be a little careful
here.

Ah.

Well, that's true.

But then we have to add one more time.

One more sentence.

The computer theory version of this will
require, in addition, that every input

does not cause an infinite loop and has an
output.

The computer.

Davis calls this pair of information,
meaning the instruction point,

where are the point, the point that you're
at, which command are you at?

The instruction point.

And the listing of variable values in
memory, a snapshot.

Deterministic algorithms are based on a
snapshot and have only one, and have one

and only one possible instruction to
execute.

It's completely determined and
well-defined.

Now, okay, just as a little note,
just to remind you, the CPU is actually

comprised of two
components, the control unit

and the ALU, the
arithmetic logical unit.

The purpose of the
control unit is to keep track

of which instructions
should be executed next.

Okay?

So that's a little bit
more detail in terms of the

actual hardware that's
relevant to our discussion.

Okay.

Back to non-deterministic.

So that's deterministic.

Non-deterministic algorithms have a
situation where, given a snapshot,

again, that means the point of code that
you're up to, the line of code that you're

up to, that you're executing, and the
values in memory at that point,

it is not determined precisely which
instruction to execute.

This leaves the possibility
for more than one choice to

be valid as part of the
programming code at this point.

Because a snapshot involves both next
instruction as well as listing of

variables, the non-deterministic choices
can actually affect either aspect.

Non-determinism is in either aspect.

It's not only... we've
always talked about the

aspect where you're
executing a line of code.

You want to know which
control unit wants to decide which

of the lines of code of the
programming should execute next.

And it finds itself in a situation where
there's more than one possibility.

So that's next instruction.

But non-determinism could also be the
listing of the variables.

In other words, a non-deterministic
function could assign the value of 3 to x,

but could also, in parallel universes,
assign the value of 5 to x.

So it's not just which
instruction you execute

next, but also what
value you have next.

Anyway, the non-deterministic choices
can... okay, as we said, okay.

Fine.

We'll discuss that and then give you some
references.

Okay, here we go.

According to Dijkstra, based on Floyd,
those two papers that I refer to...

actually one is a book.

Anyway, deterministic and
non-deterministic computation can be

understood within the rubric of standard
programming.

In other words, we could take Java,
for example, and we could make an

emendation so that we have
non-deterministic Java.

How would this work?

Well, basically njava,
non-deterministic Java, right, would be

basically identical to
deterministic Java, the regular Java.

What's the difference?

The only difference, and that's the
amazing part, you know, from a programming

point of view, there's only... it's a
whopper of a lot of a command,

but there's only one extra command that we
need to consider to implement in computer

science, our understanding of
non-determinism.

And what is that one line?

What's that one line?

The one line is as follows.

Choose a value for x...

We tell the computer, that's our command,
on line 27.

Choose a value for x from a set of values
x1 through xn, such that some Boolean

predicate p of xi is true, where p of xi
is some user-defined Boolean function.

Okay?

All other commands in njava are identical
to Java.

Identical.

So that's it.

It's a whopper, you know, and njava is
like Java.

It has loops, it has methods, it has
classes, it has object-oriented

programming, such as inheritance, it can
do recursion, it has the whole nine yards.

The one extra line, and it's a whopper,
it's an unbelievable line, but you could.

..

this one extra line is that
choose a value for x from a

set of values such that the
Boolean predicate is true.

Okay?

Now, certain assumptions.

We will be able to conclude our discussion
on time.

We're not gonna... we're
only starting with the definition,

and then we'll deal with
applications in the future classes.

Certain assumptions
have to be made in order to

understand the special
non-deterministic command.

So that should be meaningful.

One, what we said before, garbage in,
garbage out.

If you trick and purposely or innocently
give the wrong information, this

magnificent, fantastic, you know, concept
called non-determinism won't get it right.

Non-determinism won't fix your errors.

It will only help you make a decision that
you could have made.

It will just do it more efficiently.

So garbage in, garbage out.

If you do not give the right values to
choose from, so then the non-deterministic

computer is not gonna choose the right
value.

Okay?

The programmer could have a bad logic,
and there'll be errors in the code.

Non-deterministic Java could have errors.

Non-deterministic Java could have compiler
errors.

It could have logic errors due to the
user.

It's just that the choose command won't
have an error.

But you could... but...

Meaning, it'll do what you tell it to do.

But if you gave it the wrong values,
or your user-defined function isn't

correct, don't blame non-determinism for
getting the wrong answer.

Okay, number one.

Number two.

So basically, it follows number one.

The choice selected by the non-term...
well, it doesn't really follow that.

But anyway, the
choice selected by the

non-deterministic
computation is always correct.

That is unbelievable.

So that's the major assumption.

But, as strong as that
assumption sounds,

the reality is, it's not
as big as you think.

Okay, why?

I just want to think for a second.

The reason number three.

And number three, which we pointed in the
previous... in the previous set of the

tab, which is that you
may consider this the

most... you know,
unbelievable, magical concept.

But Turing realized that it isn't.

Because your deterministic computer could
simulate it by doing a brute force

exhaustive search and trying every
possibility.

If you have enough memory and enough
threads, you could execute in parallel.

Turing didn't do it in parallel, although
he did use multiple tapes to prove this.

So he was simulating parallelism,
but he was sequential.

But certainly, you can do this in
parallel.

Let your... you know, have a lightweight
thread or a heavyweight thread,

as it's called, and let each thread operate
with its own individual instruction.

And whichever one gets the solution,
let it scream, I found the solution.

And that's the solution to your
non-deterministic decision.

Right?

So the bottom line is that the cost of
this choose command is the issue.

How much time will it take?

Right?

So in non-determinism, it's the...

The non-deterministic program takes only
constant time.

All right.

I see here that it's the end of class.

And there's a little bit more that I want
to discuss, which we will.

I'll send you these notes anyway.

Although, from this
point on, I'm going to

want to review this one
more time next class.

All right?

But let's stop here.

You have enough that you can read the
notes.

And I'll send you these notes.

Maybe I'll edit this out and put this into
next class.

Part of it.

Okay.

We'll discuss that.

Anyway, it's the end of class.

So if you didn't have a chance,
kindly text that you were present.

And we will continue our discussion next
week.

I think we have class next week.

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

Let me just check our calendar to see if
we have class next week.

Next week is the 9th.

And yes, we have class.

Okay.

Next we have class.

A week from tomorrow, the college is
closed.

And then the Monday afterwards,
Monday and Tuesday, it turns out.

All right.

The class is closed for various
presidential and other holidays, I guess.

But it doesn't...

Well, the Monday the 16th will affect us,
but not the 12th of the 17th.

Anyway, again, please text you if you were
present.

And thank you.

And we will continue on Monday.

And I'll send you the notes later today.

Okay?

Thank you all.

Yes, Keith, you're right.

I worked all day yesterday and I'm very
close.

I know it sounds like a broken record
player, meaning a repeating song,

repeating words.

But my intent, and this I really mean
sincerely, is that this afternoon when I

send you the notes,
everything will be

available today, this
afternoon on Brightspace.

It just takes a long time.

I'm not making an excuse.

I should have planned it better during the
break.

But it just takes much longer than I
anticipate.

Thank you, Keith.

You had every right.

And I thank you for reminding me.

It's too cold, okay.

Bye, all.

Thank you, Keith.

Okay, bye, all.