程序代写代做代考 algorithm Java math

math

First Order Logic
Jeff Edmonds
York University

Many Courses
Lecture 0

Key to Many Courses
Predicates, Forall, & Exists
 vs 
The Proof Game
Negations
Reals
Games
Classifying Functions
Computable & Uncomputable
Time Complexity
Church’s Thesis

1

Easy.
I choose a trillion trillion.

Say, I have a game for you.
We will each choose an integer.
You win if yours is bigger.
I am so nice, I will even let you go first.
Well done. That is big!

Understand Quantifiers!!!
But I choose a trillion trillion and one
so I win.

2

You laugh but this is
a very important game
in theoretical computer science.
You choose the size of your Java program.
Then I choose the size of the input.
Likely |I| >> |J|
So you better be sure your Java program can handle such long inputs.

Understand Quantifiers!!!

3

The first order logic we can state
that I win the game:
“x, $y, y>x

The proof:
Let x be an arbitrary integer.
Let y = x+1
Note y = x+1 >x

Understand Quantifiers!!!
Good game.
Let me try again. I will win this time!

4

Understand Quantifiers!!!
Loves(Sam,Mary) = False
Loves(Sam,Beth) = True
A relation/predicate
returns True/False
depending whether objects
b and g have relation Loves.
Loves(b,g)

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

5

Understand Quantifiers!!!
Loves(b,g)

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

“b, Loves(b,Beth)
“Every boy loves Beth”
b, Loves(b,Mary)
b, Loves(b,Beth)
“b, Loves(b,MM)
“There exists a boy that loves Mary”
True
False
True
False

6

Understand Quantifiers!!!

One girl
His special woman.

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Could be a separate girl.
In all three examples,
every boy loves a girl.
The difference?

7

Understand Quantifiers!!!

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

One girl
His special woman.
“There is a girl whom every boy loves”
“For each boy, there is a girl.”

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Could be a separate girl.
Not clear.

“There is a inverse (eg 1/3) for all reals.”
“For each person, there is God.”

8

Understand Quantifiers!!!

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

One girl

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

His special woman.

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Could be a separate girl.
$g, “b, Loves(b, g)
“b, $g, Loves(b, g)

9

Understand Quantifiers!!!

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

One girl
$g,
“b, Loves(b, g, )
Let’s understand this deeply

Which variable is this statement about?:
boy b
girl g
time date
Here the date is considered free variable
because it is not bounded by a $ or a ” quantifier.
Hence, the sentence says something about date.

date
= true
= false

10

Understand Quantifiers!!!

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

One girl
$g,
“b, Loves(b, g)
Let’s understand this deeply

Which variable is this statement about?:
boy b
girl g
There are no free variables and hence depending on the world, this is either true or false.

$g is the left most quantifier. Hence,
this statement is “about” the collection of girls,
i.e. the existence of at least one with some property.
[
]

11

Understand Quantifiers!!!

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

One girl
“b, Loves(b, g)
Let’s understand this deeply

Which variable is this statement about?:
boy b
girl g
Girl g would have been a free variable,
but g denotes a specific girl like MM.

“b is the left most quantifier. Hence,
this statement is “about” the collection of boys,
i.e. that all of them have some property.

12

Understand Quantifiers!!!

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

One girl
Build understanding by building the statement backwards.
What does each subsequence say about its free variables.
(with little emphasis on the bound variables.)

Loves(b, g)
“b, Loves(b, g)
$g, “b, Loves(b, g)
$g,
“b, Loves(b, g)
“boy b loves girl g”.
“girl g is loved by all boys”.
“there is girl that is loved by all boys”.

13

Understand Quantifiers!!!

“b, $g, Loves(b, g)
$g,

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

His special woman.
“b, Loves(b, g)
$g, “b, Loves(b, g)
“boy b loves girl g”.
“girl g is loved by all boys”.
“there is girl that is loved by all boys”.
$g, Loves(b, g)
“b, $g, Loves(b, g)
“boy b loves some girl”.
“every boy loves some girl”.
Loves(b, g)
“b, Loves(b, g)
Build understanding by building the statement backwards.
What does each subsequence say about its free variables.
(with little emphasis on the bound variables.)

14

Understand Quantifiers!!!

Proof:
“b, $g, Loves(b, g)
Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

I must insist that you prove this using the following game.
Two players:
a prover and a disprover.

15

Understand Quantifiers!!!

Proof:
“b, $g, Loves(b, g)
Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

They read the statement left to right.

I produce the object when it is a $.
I produce the object when it is a “.
I can always win
if and only if
statement is true.

16

Understand Quantifiers!!!
Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Proof:
“b, $g, Loves(b, g)
No! I produce b=Bob.
Knowing you chose Bob,
I produce g = Marilin Monro
Bob loves MM so I win.
g=Mary
and I still win.
b=John!
true

17

Understand Quantifiers!!!
Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Proof:
“b, $g, Loves(b, g)
Ha ha
You need to go first now!
I produce g = MM
Nope. b=John
does not love her
true

The order the players go
REALY matters.
$g, “b, Loves(b, g)
false

18

Understand Quantifiers!!!
Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Proof:
“b, $g, Loves(b, g)
I could only win this game if there was a single girl loved by every boy.
true

The order the players go
REALY matters.
$g, “b, Loves(b, g)
false
Yup

19

Understand Quantifiers!!!

Proof:
“b, $g, Loves(b, g)
true
$g, “b, Loves(b, g)
false
Good. Now I produce g=MM.
Knowing MM, I produce boy b.
I prove b loves MM.
I can always win.
Hence, statement is true.
Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

true

20

Understand Quantifiers!!!
Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

“b, $g, Loves(b, g)

Assume A and prove B.
Sam
Beth
Fred
Ann
Prove:
A  B

A
If A is true, then there is a strategy for the game.
i.e. for any b requested,
the strategy responds with a g
such that Loves(b, g) is true.

21

Understand Quantifiers!!!
$g, “b, Loves(b, g)
= “g, Ø[ “b, Loves(b, g) ]
Ø[ ]
= “g, $b, Ø[ Loves(b, g) ]
= “g, $b, ØLoves(b, g)
$ ”

Ø moves right

Negations:
= 

22

“x, $y, x+y=0
Reals
$y, “x, x+y=0
$y, “x, x+y=x

Build understanding by building the statement backwards.
What does each subsequence say about its free variables.
(with little emphasis on the bound variables.)
x+y=0
$y, “x, x+y=0
x+y=x
$y, x+y=0
“x, $y, x+y=0
“x, x+y=0
“x, x+y=x
$y, “x, x+y=x
“y is the additive inverse of x”.
“x has an additive inverse”.
“Every real has an additive inverse”.
x+y=0
“x is the additive inverse of y”.
“Every real is an additive inverse of y.
“Some real has every real as an inverse”.
“Adding y does not change x”.
“Adding y makes no changes”.
“There is an additive zero”.
2 -2

23

Proof:
“x, $y, x+y=0
Let x be an arbitrary real number.
Reals
Let y = -x.
The relation is true.
x+y = x + (-x) = 0
I can always win.
Hence, the statement is true.
“Every real number has an additive inverse.”

true (additive inverse)

24

Proof:
“x, $y, x+y=0
Reals
true (additive inverse)

The order the players go
REALY matters.
$y, “x, x+y=0

25

Proof:
“x, $y, x+y=0
Reals

$y, “x, x+y=0
Let x=-y+1
Let y = ??? aaah
The relation is false.
x+y = (-y+1) + y ≠ 0
I can always win.
Hence, the statement is false.
false
true (additive inverse)

26

Proof:
“x, $y, x+y=0
Reals

$y, “x, x+y=0
Again, I could only win this game if there was a single y that works for every x.
Yup
false
true (additive inverse)

27

Proof:
“x, $y, x+y=0
Reals

$y, “x, x+y=0
$y, “x, x+y=x
Let y = 0.
true (additive zero)
false
true (additive inverse)
Then x+y=x is true
for all y.
Many students answer this.
But NO!
I insist that you play the game.

28

Proof:
“x, $y, x+y=0
Reals

$y, “x, x+y=0
$y, “x, x+y=x
Let x be an arbitrary real number.
Let y = 0.
The relation is true.
x+y = x + (0) = x
true (additive zero)
See there is my single y that works for all x.
false
true (additive inverse)

29

Reals
“x, $y, x×y=1
$x,”y, x×y  1

Build understanding by building the statement backwards.
What does each subsequence say about its free variables.
(with little emphasis on the bound variables.)
x×y=1
x×y  1
$y, x×y=1
“x, $y, x×y=1
“y, x×y  1
$x,”y, x×y  1
“y is the multiplicative inverse of x”.
“x has an multiplicative inverse”.
“Every real has an multiplicative inverse”.
“y is not the multiplicative inverse of x”.
“Everything fails to be x’s mult inverse”.
“There is a real without x’s a mult inverse”.
“x’s does not have a mult inverse”.

Namely zero.
What about zero.
½

30

Reals

“Every real has an additive inverse
except for zero.”
“x, property(x)
“x has an additive inverse
x is zero.”
property(x)
or
($y, x×y=1)

or (x=0)
($y, x=0) ?
$y, x=0 or x×y=1

True for all reals.

31

Reals
“x, $y, x=a or x×y=1
$a,

“Every real has an additive inverse
except for zero.”
“x,
$y, x=0 or x×y=1
with one exception.”

32

Reals
Proof:
“x, $y, x×y=1
Let x be an arbitrary real number.
(multiplicative inverse)

Let y = 1/x.
The relation is true.
x×y = x × 1/x = 1
I can always win.
Hence, the statement is true.
What a minute the statement is false!

33

Reals
Let x=0.
Let y be an arbitrary real number.
I can always win.
Hence, the negated statement is true
and the original statement is false.
Ø[ “x, $y, x×y=1 ]
= $x, “y, x×y  1
The negated relation is true.
x×y = 0×y = 0  1

Proof:

34

Reals
How about
“Every real number has a multiplicative inverse
except for zero”

“x, $y, x=a or x×y=1
$a,
Proof:

35

Reals
Let a=0.
Let x be an arbitrary real number.
I can
always win.
Hence,
the statement
is true.
x=a or x×y=1 is always true.
If x= 0, then x=a.
Else x×y = x×1/x = 1
Proof:
“x, $y, x=a or x×y=1
$a,
If x= 0, let y=5.
Else let y= 1/x .

36

White moves.
Black moves.
White wins
Playing Game

Who wins?

Black wins

White moves.
Black moves.
White wins
Playing Game

Who wins?

Black wins

White moves.
Black moves.
White wins
Playing Game

Who wins?

Black wins

White moves.
Black moves.
White wins
Playing Game

Who wins?

Black wins

“M1w, $M1b, Black-Wins(M1w,M1b)
M1w
M1b
Black has a
winning strategy

White moves.
Black moves.
White wins
Playing Game

Who wins?

White wins
$M1w, “M1b, White-Wins(M1w,M1b)
M1w
M1b
White has a
winning strategy

$M1w, “M1b, $M2w, “M2b, $M3w, “M3b, White-Wins(…

Classifying Functions
f(n) is sandwiched between c1g(n) and c2g(n)
for some sufficiently small c1 (= 0.0001)
for some sufficiently large c2 (= 1000)

f(n) = θ(g(n))

42

Classifying Functions

f(n) = θ(g(n))
For all sufficiently large n
For some definition of “sufficiently large”

43

Proof:
Classifying Functions

Let n be an arbitrary real number ≥1000
Let c=9 & n0=1000.
The relation is true.
8n2+1000n ≤ 8n2+n2 = 9n2 = cn2

See there is my single c that works for all sufficiently large n.
$c,n0, “n≥n0, 8n2+1000n ≤ cn2
true

44

Proof:
Classifying Functions

Let n=c.
Let c=10000000 & n0=1.
The relation is false.
2n > n∙n = cn

$c,n0, “n≥n0, 8n2+1000n ≤ cn2
$c,n0, “n≥n0, 2n ≤ cn
false
true

45

Proof:
Classifying Functions

$c,n0, “n≥n0, 8n2+1000n ≤ cn2
$c,n0, “n≥n0, 2n ≤ cn
“n, $c, 2n ≤ cn

The order the players go
REALY matters.
false
true

46

Proof:
Classifying Functions

Let n=10000000
Let c=2n.
The relation is true.
2n ≤ 2nn = cn

$c,n0, “n≥n0, 8n2+1000n ≤ cn2
$c,n0, “n≥n0, 2n ≤ cn
true
“n, $c, 2n ≤ cn
false
true

47

Theta f(n) = θ(g(n)) f(n) ≈ c g(n)
BigOh f(n) = O(g(n)) f(n) ≤ c g(n)
Omega f(n) = Ω(g(n)) f(n) ≥ c g(n)
Little Oh f(n) = o(g(n)) f(n) << c g(n) Little Omega f(n) = ω(g(n)) f(n) >> c g(n)

Giving an idea of how fast a function grows without going into too much detail.

Classifying Functions

48

Classifying Functions

$ c1, c2, n0, ” n ³ n0 nc1 £ f(n) £ nc2
3n2 + 7n + 8 = nθ(1)
Polynomial time

49

Classifying Functions

$ c1, c2, n0, ” n ³ n0 2c1n £ f(n) £ 2c2n
3n n = 2[ log(3) n + log n ]
= 2θ(n)
Exponential time

50

A Computational Problem P states
for each possible input I
what the required output P(I) is.

An Algorithm/Program/Machine M is
a set of instructions
(described by a finite string “M”)
on a given input I
follow instructions and
produces output M(I)
or runs for ever.

Eg: Sorting
Eg: Insertion Sort
Computable Problem

Computable Problem
$M,
Problem P is
computable if

M(I)=P(I)
“Machine/Algorithm M
gives the answer required
by problem P on input I.”
“Machine/Algorithm M
computes problem P.”
“I,
M(I)=P(I)
“I,
$M,

52

I have a machine M that I claim works.
I win if M on input I gives
the correct output
Oh yeah, I have an input I for which it does not.
M(I)=P(I)
“I,
$M,
Computable Problem
Problem P is
computable if

What we have been doing all along.

53

$M
I come up with this machine M at compile time.
Without knowing the input!
It needs a finite description.
Finite set of instructions
Finite set of variables
With finite ranges of values.
M(I)=P(I)
“I,
$M,
Computable Problem
Problem P is
computable if

54

“I
I choose the input I at run time
after I already know the machine M.
My input can be much bigger
than the machine.
Its computation may require
a lot more memory to be allocated dynamically.
at lot more time.
M(I)=P(I)
“I,
$M,
Computable Problem
Problem P is
computable if

55

M(I)=P(I)
“I,
$M,
Computable Problem
Problem P is
computable if

Here the P is considered free because it is not bounded by a quantifier.
Hence, the sentence says something about P.

56

“M, $I, M(I)  P(I)
M(I)=P(I)
“I,
$M,
Problem P is
uncomputable if
I win if M on input I gives
the wrong output
I have a machine M that I claim works.
I find one counter example input I for which
his machine M fails us.
Computable Problem
Problem P is
computable if

Generally very hard to do.

57

“M, $I, M(I)  Halting(I)
M(I)=Sorting(I)
“I,
$M,
Computable Problem
“I, $M, M(I) = Halting(I)

The order the players go
REALY matters.
If you don’t know if it is true or not, trust the game.
true
Problem P is
uncomputable if
Problem P is
computable if
true

58

“M, $I, M(I)  Halting(I)
Given I either
Halting(I) = yes or
Halting(I) = no.
I give you an input I.
“I, Myes(I) says yes
“I, Mno(I) says no
Computable Problem
“I, $M, M(I) = Halting(I)
I don’t know which, but one of these does the trick.
true
true
M(I)=Sorting(I)
“I,
$M,
Problem P is
computable if
true
Problem P is
uncomputable if

A tricky one.

59

Problem P is computable in n2 time.
M, “I, M(I)=P(I) & Time(M,I)≤|I|2
M, “I, [M(I)=P(I)]  [Time(M,I)>|I|2]
Time Complexity
Problem P is not computable in n2 time.
No
M, [If M solves P]  [M takes > n2 time]

M, [“I M(I)=P(I)]  [“I Time(M,I)>|I|2]

60

Problem P is computable in n2 time.
M, “I, M(I)=P(I) & Time(M,I)≤|I|2
M, I, M(I)≠P(I) or Time(M,I)>|I|2)
Time Complexity
Problem P is not computable in n2 time.
Let M be any machine.
Either because it gives the wrong answer or takes too much time.

Just negate the above statement!

I find one counter example input I for which his machine M fails us.

61

Computable with Fixed Resources

Computable mean
that some algorithm computes it.

Computable with Fixed Resources

Note that the number of line in a print out of the code
does not actually depend on the input

Computable with Fixed Resources

These are the types of things we will be saying with our first order logic statements.

Computable with Fixed Resources

Computable with Fixed Resources

Computable with Fixed Resources

Computable with Fixed Resources

Computable with Fixed Resources

Computable with Fixed Resources

Halting problem poly Math Truth
“TM M halts on input I”
=  C, “C is an integer encoding
a valid halting computation
for TM M on input I”

 “time t” “a legal TM
M step is taken”

Harder for 4111

Problem P is computable in polynomial time.

Problem P is not computable in polynomial time.

Problem P is computable in exponential time.

The computational class “Exponential Time”
is strictly bigger than the computational
class “Polynomial Time”.
 M, c, n0,”I, M(I)=P(I) & (|I| < n0 or Time(M,I) ≤ |I|c)  M, c, n0,  I, M(I)≠P(I) or (|I| ≥ n0 & Time(M,I) > |I|c)
 M, c, n0,”I, M(I)=P(I) & (|I| < n0 or Time(M,I) ≤ 2c|I|) [ M, c, n0,  I, M(I)≠P(I) or (|I| ≥ n0 & Time(M,I) > |I|c)]
[ M, c, n0,”I, M(I)=P(I) & (|I| < n0 or Time(M,I) ≤ 2c|I|)]  P, & Time Complexity 73 Church’s Thesis If a boy can do it, a girl can do it better. If a Java program can do it, Turing Machine can simulate it. A computational problem is computable by a Java Program by a Turing Machine Church’s Thesis A computational problem is computable by a Java Program by a Turing Machine Why are these the same? Church’s Thesis Why are these the same? Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof Proof End Understand Quantifiers!!! Ann Fred Marilin Monro John Beth Bob Mary Sam Proof: $g, "b, Loves(b, g) I produce girl MM. Let b be an arbitrary boy. I give an “alg” with input b, and output a proof that Loves(b,MM) 105 Understand Quantifiers!!! Ann Fred Marilin Monro John Beth Bob Mary Sam Proof: "b, $g, Loves(b, g) Let b be an arbitrary boy. I give an “alg” with input b, and output an g and a proof that Loves(b, g). You give Sam, I give Beth. You give Bob, I give MM. … 106 Understand Quantifiers!!! Proof: "b, Loves(b, MM) I don’t like proving universal (") statements by contradiction. By way of contradiction assume b, ØLoves(b, MM) Let b’ be the object that is assumed to exist. Prove Loves(b’,MM) Contradiction. Hence, true. Ann Fred Marilin Monro John Beth Bob Mary Sam Instead play the game. 107 Negations: What is the negation of this? "bBoys, Loves(g) $bBoys, ØLoves(b, g) No, we are still talking about properties of the b in the set Boys. Understand Quantifiers!!! 108 Negations: What is the negation of this? "x $yx, y=2x No, we are still talking about properties of the y that are bigger than x. $x "y0, $y, x×y=1
changing the range of x,
is more like 2nd order logic.

110

Understand Quantifiers!!!

If you say “x,
then is x=0 a possibility.
“x, $y, x×y=1
“x, [x0] and [$y, x×y=1]

How about
“Every real number has a multiplicative inverse
except for zero”

111

Understand Quantifiers!!!

We need this statement true
for every value of x!
“x, $y, x×y=1
“x, [x=0] [$y, x×y=1]

or

How about
“Every real number has a multiplicative inverse
except for zero”

112

Understand Quantifiers!!!
“x, $y, x×y=1
“x, $y, x=0 or x×y=1

Usually we prefer the quantifiers
to be on the outside.
“x, [x=0] [$y, x×y=1]
or

How about
“Every real number has a multiplicative inverse
except for zero”

113

Understand Quantifiers!!!
“x, $y, x×y=1
“x, $y, x=0 or x×y=1
“x, $y, x=a or x×y=1
$a,
“x, [x=0] [$y, x×y=1]
or

How about
“Every real number has a multiplicative inverse
except for zero”

114

Understand Quantifiers!!!

“b, Loves(b, g)
“Every boy loves g”
b vs g?
b is a bound variable.
(appears in  or )
The statement is about
the set of all boys.

x=5
loop i = 1..9
++x
end loop

Bound variable
Object

Free variable

g is a free variable.
(does not appear in  or )
The statement is about g.

115

Understand Quantifiers!!!

“b, Loves(b, g)
g is a free variable.
(does not appear in  or )
The statement is about g.
VeryLoved(g) = “b, Loves(b, g)
A relation/predicate
returns True/False
depending whether object
g has the property VeryLoved.

116

Classifying Functions

3n2 + 7n + 8 = θ(n2)
3
4
8

3·n2 £ 3n2 + 7n + 8 £ 4·n2
n ³ 8
True
7n + 8 £ 1·n2
7 + 8/n £ 1·n

117

Classifying Functions

3n2 + 7n + 8 = θ(n2)

118

Classifying Functions

3n2 + 7n + 8 = θ(n)

The reverse statement

119

Implications
A  B
If A is true then B is true.
This may because A causes B.
The counter positive is B  A
because if B is not true, then A can’t be true
because otherwise B would be true.
Hence B may cause A.
Or C may cause both A and B.
Or maybe cause and effect is not involved at all.
A ⇒ B formally means ¬(A and ¬B)
Bring the negation in gives ¬A or B
If A is false, then the statement A ⇒ B follows.
If B is true, then A ⇒ B again follows.

120

Implications
Proof of A  B
Officially two cases.
If A is false, then A ⇒ B is trivially true.
If A is true, one must prove B.
Indenting, pushing and popping stack.
A proof consists of a sequence of statements
that follow from the initial assumptions.
When we make the new assumption A,
indents the lines for the duration
of this new assumption.
Then after B is proved,
this indenting “stack” is popped
with the conclusion that A ⇒ B.
ignore

121

Implications
Proof of A  B
Goal is to prove A ⇒ B.
Assume that A is true.
Goal is to prove B.
… proof of B.
Hence B is true.
Hence A ⇒ B is true.

122

Implications
Suppose you assume this is true:
S1: “x, P(x)

Then you know that P(x’) is true for your favorite value x′.
Suppose you assume this is true:
S2: $y, Q(y)

Then you can ask for a y’
for which Q(y’) is true.

123

Implications
Suppose you assume this is true:
S3: “x, $y, R(x,y)

You can use it as an oracle.
If you have an x’, it gives you a y’.
“Let y’ be the value assumed to exist from S3
By definition of y’, we know that
R(x’,y’)

124

Implications

125

Quantifiers,
Do you understand them?

“A(I)=P(I)”means algorithm A gives the required
output for problem P on instance I.
Time(A,I) is the running time of algorithm A
on instance I.
T(n) some function like n2.
Express:
Problem P is computable by some algorithm.
Problem P is computable in time T(n).
Problem P is computable in polynomial time.
The computational class “Exponential Time”
is strictly bigger than the computational
class “Polynomial Time”.

The Time Complexity
The minimum time needed by an algorithm to solve it.

Problem P is computable in time Tupper(n)
if there is an algorithm A which
outputs the correct answer
in this much time
given any input instance I.
Eg: Sorting computable in Tupper(n) = O(n2) time.
Upper Bound:

127

A(I)=P(I)
Upper Bound:
The Time Complexity

We need our algorithm A
to give the correct answer
to problem P
on input I

128

A(I)=P(I)
Upper Bound:
The Time Complexity

We need it to run
in say n2 time.

Time(A,I) £ n2

129

A(I)=P(I)
Upper Bound:
The Time Complexity

But what is n?

Time(A,I) £ Tupper(|I|)
Time(A,I) £ n2

130

A(I)=P(I)
Upper Bound:
The Time Complexity

Between these?

Time(A,I) £ Tupper(|I|)
and

131

A(I)=P(I)
Upper Bound:
The Time Complexity

What do we want from our algorithm A?
Where does it come from?

Time(A,I) £ Tupper(|I|)
and
I want to prove the statement is true.
I want the algorithm
to be one that works well,
so I will come up with it.
$A

$A,

132

A(I)=P(I)
Upper Bound:
The Time Complexity

What do we want from our input I?
Where does it come from?

Time(A,I) £ Tupper(|I|)
and
I want to prove the statement is false. I want the input to be the worst,
so I will come up with it.
“I

“I,
$A,

133

A(I)=P(I)
Upper Bound:
The Time Complexity

Who goes first
and why?

Time(A,I) £ Tupper(|I|)
and
I want one fixed algorithm that works for every input,
so I should go first.
“I,
$A,

134

A(I)=P(I)
Upper Bound:
The Time Complexity

Time(A,I) £ Tupper(|I|)
and
I want my input to be
the worst for his algorithm
so I should go second.

“I,
$A,
“I,
$A,
Who goes first
and why?

135

A(I)=P(I)
Upper Bound:
The Time Complexity

What do we want from our problem P?
Where does it come from?

Time(A,I) £ Tupper(|I|)
and

We are making a statement about P.
It comes our boss.

“I,
$A,

136

A(I)=P(I)
Upper Bound:
The Time Complexity

How does
the proof game go?

Time(A,I) £ Tupper(|I|)
and
“I,
$A,

137

A(I)=P(I)
Upper Bound:
The Time Complexity

I have an algorithm A that I claim works and is fast.
I win if A on input I gives
the correct output
in the allotted time.
Oh yeah, I have an input I for which it does not.
What we have been doing all along.
Time(A,I) £ Tupper(|I|)
and
“I,
$A,

138

The Time Complexity
The minimum time needed by an algorithm to solve it.
Time Tlower(n) is a lower bound for problem p
if no algorithm solves the problem faster.
There may be algorithms that give the correct answer
or run quickly on some inputs instance.
Lower Bound:

139

The Time Complexity
The minimum time needed by an algorithm to solve it.
Eg: No algorithm can sort N values
in Tlower = sqrt(N) time.
But for every algorithm, there is at least one instance I for which either the algorithm gives the wrong answer or it runs in too much time.
Time Tlower(n) is a lower bound for problem p
if no algorithm solves the problem faster.
Lower Bound:

140

$A, “I, A(I)=P(I) and Time(A,I) £ Tupper(|I|)
“A, $I, A(I) ≠ P(I) or Time(A,I) ³ Tlower(|I|)
Lower Bound:
Upper Bound:
The Time Complexity
The minimum time needed by an algorithm to solve it.

“There is”and “there isn’t a faster algorithm”
are almost negations of each other.

141

The Time Complexity

How does
the proof game go?

“A, $I, [ A(I)  P(I) or Time(A,I) ³ Tlower(|I|)]
Lower Bound:

142

Lower Bound:
The Time Complexity

I win if A on input I gives
the wrong output or
runs slow.
“A, $I, [ A(I)  P(I) or Time(A,I) ³ Tlower(|I|)]
I have an algorithm A that I claim works and is fast.
Oh yeah, I have an input I for which it does not .

143

Lower Bound:
The Time Complexity

“A, $I, [ A(I)  P(I) or Time(A,I) ³ Tlower(|I|)]
I have an algorithm A that I claim works and is fast.
Lower bounds are very hard to prove, because I must consider every algorithm
no matter how strange.

144

Problem P is computable in polynomial time.
 A, “I, A(I)=P(I) & Time(A,I) ≤ |I|c
The Time Complexity

Great, but which c?

I want to prove the statement is true
so I will come up with it.
$c

Wow. That’s not fair.
A bigger c can always
make the statement true.
 c,

145

The Time Complexity

Who goes first
and why?

Problem P is computable in polynomial time.
 A, “I, A(I)=P(I) & Time(A,I) ≤ |I|c
I will let him choose any c.
Even c=1000 if he wants.
But this fixed c must work for all inputs.
So I should go second.

 c,
 c,

146

The Time Complexity

Who goes first
and why?

Problem P is computable in polynomial time.
 A, “I, A(I)=P(I) & Time(A,I) ≤ |I|c
If he comes up with
a bigger c,
I will come up with
an even bigger I.
 c,

147

The Time Complexity

Problem P is computable in polynomial time.
 A, “I, A(I)=P(I) & Time(A,I) ≤ |I|c
 c,
Time(A,I) ≤ |I|c
Does not apply for small I.

148

The Time Complexity

Problem P is computable in polynomial time.
Time(A,I) ≤ |I|c
Does not apply for small I.
 A, c, “I, A(I)=P(I) & (|I| < n0 or Time(A,I) ≤ |I|c) What about n0? n0, 149 Problem P is computable in polynomial time. Problem P is not computable in polynomial time. Problem P is computable in exponential time. The computational class “Exponential Time" is strictly bigger than the computational class “Polynomial Time”.  A, c, n0,"I, A(I)=P(I) & (|I| < n0 or Time(A,I) ≤ |I|c)  A, c, n0,  I, A(I)≠P(I) or (|I| ≥ n0 & Time(A,I) > |I|c)
 A, c, n0,”I, A(I)=P(I) & (|I| < n0 or Time(A,I) ≤ 2c|I|) [ A, c, n0,  I, A(I)≠P(I) or (|I| ≥ n0 & Time(A,I) > |I|c)]
[ A, c, n0,”I, A(I)=P(I) & (|I| < n0 or Time(A,I) ≤ 2c|I|)]  P, & The Time Complexity 150 Given the needs of the problem at hand, a programmer can give her Java program as many lines of code as many variables and as a big of a (finite) range for each variable as she wants. But these numbers are fixed/constant. If K(J,I) is these numbers program J has on input I, then this function can depend on J, but can’t depend on I (or on |I|) Meaning: Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I) = k Given the needs of the problem at hand, a programmer can give her Java program as many lines of code as many variables and as a big of a (finite) range for each variable as she wants. But these numbers are fixed/constant. If K(J,I) is these numbers program J has on input I, then this function can depend on J, but can’t depend on I (or on |I|) Meaning: Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I) = k number of lines actually used by J on I. K(J,I) does depend on I.  Clearly J can’t use more lines than the number k that it actually has. But these numbers are fixed/constant. Meaning: Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I)  k Remember that we say that f(n) = 5+sin(n)  (1) because, though f(n) is not actually constant wrt n, it is bounded above by a constant. In a “bigOh” sort of way, we might still say that K(J,I) is a fixed/constant number. Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I) = k I come up with a hard problem P Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I) = k I write a Java program J and give it some k lines of code. I can use as MANY as I like. 1,000,000,000,000,000! Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I) = k I write a Java program J and give it some k lines of code. I can use as MANY as I like. 1,000,000,000,000,000! Wow. That’s not fair. With more and more code, you can memorize more and more answers. Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I) = k I write a Java program J and give it some k lines of code. I can use as MANY as I like. 1,000,000,000,000,000! I will let him use any number of lines he wants, But this fixed J must work for all inputs. Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I) = k I write a Java program J and give it some k lines of code. I can use as MANY as I like. 1,000,000,000,000,000! If he uses more lines of code, I will give him a bigger input I. Hee Hee Hee J must still solve the problem. Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J,  an integer k, "inputs I, K(J,I) = k " Java programs J,  an integer k, "inputs I, K(J,I) = k that speaks of all J, even if not associated with a P. A similar statement Given the input, a Java program, can dynamically allocated as many bytes of memory as it wants. This number, though still finite, is not constant. If K(J,I) is the number bytes program J uses on input I, then this function can depend on J, and on I. (hence on |I|) Meaning: Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J, "inputs I, K(J,I) <  Careful will infinity. There are more than one infinities and some are in fact smaller than others. Given the input, a Java program, can dynamically allocated as many bytes of memory as it wants. This number, though still finite, is not constant. If K(J,I) is the number bytes program J uses on input I, then this function can depend on J, and on I. (hence on |I|) Meaning: Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J, "inputs I, K(J,I) <  In contrast, when we say J(I) =  to mean J runs forever, we are really using ∞ as a symbol and not really as meaning it to be infinity. Given the input, a Java program, can dynamically allocated as many bytes of memory as it wants. This number, though still finite, is not constant. If K(J,I) is the number bytes program J uses on input I, then this function can depend on J, and on I. (hence on |I|) Meaning: Fixed/Constant vs Arbitrary/Finite "computable problems P,  a Java program J, "inputs I,  an integer k, K(J,I) = k Fixed/Constant vs Arbitrary/Finite I come up with a hard problem P "computable problems P,  a Java program J, "inputs I,  an integer k, K(J,I) = k Fixed/Constant vs Arbitrary/Finite I write a Java program J. I don’t need to specify how many bytes of memory k it will allocate. Oops. I now need to come up with the input I before knowing this k. "computable problems P,  a Java program J, "inputs I,  an integer k, K(J,I) = k Fixed/Constant vs Arbitrary/Finite No problem. If he gives me a bigger input I, I will use even more memory! "computable problems P,  a Java program J, "inputs I,  an integer k, K(J,I) = k Fixed/Constant vs Arbitrary/Finite No problem. If he gives me a bigger input I, I will use even more memory! Good thing he cannot increase the number of lines of code in the same way or else it would take infinite space to write down the algorithm such an algorithm could solve any problem. Fixed/Constant vs Arbitrary/Finite Home work to do starting now Home work to do starting now Home work to do starting now Home work to do starting now 3. Home work to do starting now If a boy can do it, a girl can do it better. If a Java program can do it, a Turing Machine can simulate it Home work to do starting now Understand Quantifiers!!! Fred Layton John Harper Bob Sam Could be a different politician. Fred Layton John Bob Sam One politician $politician, "voters, Loves(v, p) "voters, $politician, Loves(v, p) 174 Understand Quantifiers!!! Fred Layton John Bob Sam Fred Layton John Harper Bob Sam “There is a politician that is loved by everyone.” This statement is “about” a politician. The existence of politician with some property. The property that he is “loved by every voter”. $politician, "voters, Loves(v, p) "voters, $politician, Loves(v, p) [ ] [ ] “Every voter loves some politician.” This statement is “about” voters. Something is true about every voter. We claim that he “loves some politician.” 175 $ $ " ³ £ £ c c n n n c g n f n c g n 1 2 0 0 1 2 , , , , ( ) ( ) ( ) " " $ ³ >
>
c
c
n
n
n
c
g
n
f
n
or
f
n
c
g
n
1
2
0
0
1
2
,
,
,
,
(
)
(
)
(
)
(
)