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 ≤ 2nn = 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?
"bBoys, Loves(g)
$bBoys, Ø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 $yx, y=2x
No, we are still talking about
properties of the y
that are bigger than x.
$x "y
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, [x0] 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
,
,
,
,
(
)
(
)
(
)
(
)