程序代写代做代考 algorithm Java math

math

First Order Logic
for Computer Science
Jeff Edmonds
York University

Many Courses
Math1090,EECS2001,
3101,6111
Lecture 1

Predicates, Forall, & Exists
 vs 
Negations
Understanding from the Inside
The Proof Game
Auxilary Functions
Reals
Classifying Functions
Computable & Uncomputable
Time Complexity
Table Lookup and TM
Computable with Fixed Resources
Probabilistic Algorithms
Jeff’s Informal Proof

The point of formal proofs is
to prove theorems
with as few assumptions as possible
about the nature of the objects
we are talking about
so that we can find a wide range
of strange new objects
for which the same theorems are true.
First Order Logic
for Computer Science

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.

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!!!

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!

Understand Quantifiers!!!
Loves(b,g)

People need to
love and be loved.

Sorry this is heteronormative.

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

T T
T T
T
T T T

g
b

Understand Quantifiers!!!
Loves(b,g)

“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

T T
T T
T
T T T

g
b
Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

 vs 

One girl
His special woman.

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?

T
T
T
T

T T
T T
T T
T T T

T
T
T
T

 vs 

One girl
His special woman.

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Could be a separate girl.

T
T
T
T

T T
T T
T T
T T T

T
T
T
T

“There is a girl
whom every boy loves”
“For each boy,
there is a girl.”
Not clear.

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

 vs 

One girl
His special woman.

Ann
Fred
Marilin Monro
John
Beth
Bob
Mary
Sam

Could be a separate girl.

T
T
T
T

T T
T T
T T
T T T

T
T
T
T

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

 vs 

Fred
Layton
John
Bob
Sam

One politician
Fred
Layton
John
Harper
Bob
Sam

Could be a
different politician.

$politician, “voters, Loves(v, p)
“voters, $politician, Loves(v, p)

 vs 

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 such a politician.
We claim that this politician is “loved by everyone”.
$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.”

 vs 

$g, “b, Loves(b, g)
“b, $g, Loves(b, g)
loop g{girls} (checking true for some)
loop b{boys} (checking true for all)
Loves(b,g)
loop b{boys} (checking true for all)
loop g{girls} (checking true for some)
Loves(b,g)

T
T
T
T

g
b

T
T
T
T

g
b

 vs 

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

T
T
T
T

g
b

T
T
T
T

g
b
create Result.make_from_tuple_array (
<<["Sam", "Beth"], ["Bob", "Marilin Monro"], ["John", "Mary"], ["Fred", "Ann"]>>) — Special Woman

t1: BOOLEAN
do
— ∃g ∀b loves(b,g)
Result :=
across get_girls is g
some
across get_boys is b
all
loves (b, g)
end
end
end
end

 vs 

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

T
T
T
T

g
b

T
T
T
T

g
b
g

And

b
And

b
Or

Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)
Loves(b,g)

g
Or

g
And

 vs 

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

T
T
T
T

g
b

T
T
T
T

g
b
What might the following mean?
Loves(b, g$)

“arbitrary value” “fixed”

If g$ is really fixed,
it should work for every b.

 vs 

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

T
T
T
T

g
b

T
T
T
T

g
b

Loves(b, g$)
If g$ is really fixed,
it should work for every b.

 vs 

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

T
T
T
T

g
b

T
T
T
T

g
b

What about here?
Loves(b, g$)
Loves(b, g$ )
(b)
Here which value g$ is “fixed” to
can depends on the value of the “arbitrary” b.
Here g$(b)) is called a Skolem function.

 vs 

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

T
T
T
T

g
b

T
T
T
T

g
b

Loves(b, g$)
Loves(b, g$ )
(b)
Implied
$g$ “b [ ]
$g$ “b [ ]
This is a little non-standard,
but Jeff uses this a lot in his formal proof system.
≡
≡

Negations
$g, “b, Loves(b, g)
= “g, Ø[ “b, Loves(b, g) ]
Ø[ ]
= “g, $b, Ø[ Loves(b, g) ]
= “g, $b, ØLoves(b, g)
$ ”

Ø moves right
Negations:
= 

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.
Negations

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.

“x, $y, x×y=1

Reals

“Every real has an multiplicative inverse
except for zero.”
“x, property(x)
“x has an multiplicative 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.

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

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

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!

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:

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

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

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 .

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))

Classifying Functions

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

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

Proof:
Classifying Functions

Let n = max(c,n0,3)
Let c and n0 be arbitrary eg =10000000
The relation is false.
2n > n∙n = cn

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

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

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

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

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

Classifying Functions

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

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,

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.

$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

“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.
a lot more time.
M(I)=P(I)
“I,
$M,
Computable Problem
Problem P is
computable if

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.

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

People tend to struggle with expressing this in first order logic.
Their intuition tends to be wrong.
As such times, it is helpful to know how to mechanically follow the rules of formal logic.
Simply take the negation.

“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.

“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

“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.

“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”

Computable Problem
= all expressed as a first order logic statement.

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.
These are all false for every computable P
M, [If M solves P]  [M takes > n2 time]

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

M, [“I M(I)=P(I)]  [“I Time(M,I)>|I|2]
Let I´ = 0000000000 and P´ = P(I´)
Let M be the machine that
if (I=I´) return( P´ )
else slowly solves P
Oops
M(I)=P(I) is always true
Time(M,I)>|I|2 is false for I=I´.

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.
My mistake
M, [If M solves P]  [M takes > n2 time]

M, [“I M(I)=P(I)]  [“I Time(M,I)>|I|2]
Actually they are true
for P for which the output P(I)
contains more than |I|2 characters.

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.

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 81 ??? That does not compute!!! Table lookup is another model of computation Table Look Up and TM An algorithm is a finite table listing input,output pairs. Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 Given an input it “computes” by looking up the answer. If not there, if fails. 82 Table Look Up and TM Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 No, 25=? Can a Table multiply two arbitrary integers in one time step? Sure 24=8 83 Table Look Up and TM Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 Sure. k,  Table M, x,yk M multiplies xy. I give you the multiplication table M of size k2. I give you a value k. I give you x,yk. My table gives you xy. 84 Table Look Up and TM Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 Let M be an arbitrary table. No It better be finite in size. i.e. can’t list an infinite number of answers. Let x,y be a input that does not have an answer.  Table M, x,y M multiplies xy. 85 Table Look Up and TM Bigger numbers need software and more time. I am going to define the first model of computation. What should I let it do in one time step? Is it fair to let it multiply? Some CPUs have built into hardware a16 bit multiplier. And hence can do this in one clock cycle. Other CPUs have only simple but fast operations so that a clock cycle is fast. 86 Table Look Up and TM ?? Anything?? I will solve the halting problem in one time step. Who am I to say? Hardware had not been built in 1936. I will give the algorithm designer the choice to do in one time step anything that can be done by …. Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 table look up. Ok, But only as many answers as you are willing to put into a finite table. 87 Table Look Up and TM Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 Can your TM then solve the Halting problem? No we will prove that this is uncomputable? ??? 88 Table Look Up and TM Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 Sure. I give you the halting problem table M of size k. I give you a value k. How do you build this table when the halting problem is uncomputable? k,  TM M, Ik M in one time step can look up in a table the answer to the halting problem for I. Good point. 89 Table Look Up and TM Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 Sure. There exists a halting problem table M of size k. I give you a value k. I doubt such a thing is really anywhere. True k,  TM M, Ik M in one time step can look up in a table the answer to the halting problem for I. 90 Table Look Up and TM Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8 Sure. Of all 2k tables of k yes/no answers one of them just happens to give right answers to the halting problem. I give you a value k. I give you Ik. My table gives you Halting(I). k,  TM M, Ik M in one time step can look up in a table the answer to the halting problem for I. True. 91 Table Look Up and TM Input Output 1,1 1 1,2 2 1,3 3 2,1 2 2,2 4 2,3 6 2,4 8  TM M, I M in one time step can look up in a table the answer to the halting problem for I. Let M be an arbitrary table. No It better be finite in size. i.e. can’t list an infinite number of answers. Let x,y be a input that does not have an answer. 92 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 Probabilistic Algorithms Probabilistic Algorithms Suppose there are n doors. Half are promised to have prizes. The algorithm A specifies which doors are opened. The input I specifies which doors have prizes. The adversary, knowing your algorithm, gives you the worst case input. I have an algorithm A that I claim works. Actually my algorithm always gives the right answer and is fast. Oh yeah, I have a worst case input I for which it does not. Probabilistic Algorithms A(I)=P(I) "I, $A, Problem P is computable if & Time(A,I) ≤ T ‹#› 104 My algorithm A specifies which doors are opened. Oh dear. I know which doors you choose. My input I puts no prizes behind the first n/2 doors you look in. A(I)=P(I) "I, $A, Probabilistic Algorithms Problem P is computable if & Time(A,I) ≤ T No. Actually, I am quite mean. I really do give a worst case input. =n/2 +1 ‹#› 105 My algorithm A specifies to pivot with the middle item. Oh dear. I know this. My input I puts the smallest element in the middle. A(I)=P(I) "I, $A, Probabilistic Algorithms Problem P is computable if & Time(A,I) ≤ T No. Actually, I am quite mean. I really do give a worst case input. =n2 Remember Quick Sort ‹#› 106 I have a random algorithm A that I claim works. I know the algorithm A, but not its random coin flips R. I do my best to give you a worst case input I. "I, $A, Problem P is computable by a random algorithm if Probabilistic Algorithms The random coin flips R are independent of the input. And for EVERY input I, I want the correct answer. AR(I)=P(I) R, " My algorithm A will open all doors if necessary. ‹#› 107 I have a random algorithm A that I claim works. I know the algorithm A, but not its random coin flips R. I do my best to give you a worst case input I. "I, $A, Problem P is computable by a random algorithm if Probabilistic Algorithms The random coin flips R are independent of the input. And for EVERY input I, the expected running time (over choice of R) is great. There are worst case coin flips but not worst case inputs. AR(I)=P(I) "R, ExpectedR Time(AR,I) ≤ T ‹#› 108 I have a random algorithm A that I claim works. I know the algorithm A, but not its random coin flips R. I do my best to give you a worst case input I. "I, $A, Problem P is computable by a random algorithm if Probabilistic Algorithms AR(I)=P(I) "R, ExpectedR Time(AR,I) ≤ T Each random door has a 50% chance of finding a prize. So the expected number of doors is 2. =2 ‹#› 109 I know the algorithm A, but not its random coin flips R. I do my best to give you a worst case input I. Problem P is computable by a random algorithm if Probabilistic Algorithms I have a random algorithm A that I claim works. PrR "I, AR(I)=P(I) Some random algorithm might give the wrong answer on exponentially few random coin flips $A, ≥ 1-2-T Time(AR,I) ≤ T Each random door has a 50% chance of finding a prize. The probability of finding no prize behind T doors is 2-T ‹#› 110 A Proof System Given α, a proof of α is: A finite list strings. Handed to you by a mathematician. Has some mechanically checkable structure. A proof system is Sound iff α has a proof  it is true ⊢α  ⊨α Complete iff α is true  it has a proof ⊨α  ⊢α Jeff’s Informal Proofs ‹#› 111 Jeff’s Informal Proofs Ann Fred Marilin Monro John Beth Bob Mary Sam Proof: "b, $g, Loves(b, g) Let b be an arbitrary boy. I give a girl g, but which one depends on b. You give Sam, I give Beth. You give Bob, I give MM. … ‹#› 112 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. Jeff’s Informal Proofs r is c ‹#› 113 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. Jeff’s Informal Proofs ‹#› 114 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′. “For my x′, let y′ be the value assumed to exist from S3.” By definition of y′, we know that R(x′,y′) Jeff’s Informal Proofs ‹#› 115 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. T T T T T T T T T T T T T T T T T $g, "b, Loves(b, g) "b, $g, Loves(b, g) Jeff’s Informal Proofs A: B: A  B True B  A False ‹#› 116 His special woman. Ann Fred Marilin Monro John Beth Bob Mary Sam T T T T T T T T T T T T T T T T T $g, "b, Loves(b, g) "b, $g, Loves(b, g) One girl Ann Fred Marilin Monro John Beth Bob Mary Sam Ann Fred Marilin Monro John Beth Bob Mary Sam Could be a separate girl. Jeff’s Informal Proofs A: B: B  A " Models/Universes B and ⌐A $ Model/Universe ‹#› 117 One girl T T T T Jeff’s Informal Proofs Ann Fred Marilin Monro John Beth Bob Mary Sam A  B Prove $g, "b, Loves(b, g) "b, $g, Loves(b, g) A: B: If there is one girl that is loved by every boy, Then every boy loves at least that girl. ‹#› 118 Jeff’s Informal Proofs A  B Prove $g, "b, Loves(b, g) A: "b´, $g´, Loves(b´, g´) B: Assume A Prove B by playing the game Let b´ be an arbitrary boy. Let g´ be the girl g that I am assured of by A. Loves(b´, g) and hence Loves(b´, g´). B-Test: B-Construct: B-Prove: I’m your advisory by testing with "objects. I prove B is true by constructing the $objects and proving the final statement. ‹#› 119 Jeff’s Informal Proofs A  B Prove $g, "b, Loves(b, g) A: "b´, $g´, Loves(b´, g´) B: Assume A Prove B by playing the game Let g be the girl assumed to exist in A. Let b be the boy I need help with. By A we have Loves(b, g). A-To help: A-Get help: A-Assure: I get help by giving you "objects. I assure A is true. To help I construct the $objects and assure the final statement. ‹#› 120 Jeff’s Informal Proofs A  B Prove $g, "b, Loves(b, g) A: "b´, $g´, Loves(b´, g´) B: Assume A Prove B by playing the game Let g be the girl assumed to exist in A. Let b´ be an arbitrary boy. Let b = b´ be the boy I need help with. Let g´ = g that I got from A. By A we have Loves(b, g). Hence Loves(b´, g´). A-To help: B-Test: A-Get help: B-Construct: A-Assure: B-Prove: ‹#› 121 Jeff’s Informal Proofs A  B Prove $g, "b, Loves(b, g) A: "b´, $g´, Loves(b´, g´) B: Assume A Prove B by playing the game Let g be the girl assumed to exist in A. Let b´ be an arbitrary boy. Let b = b´ be the boy I need help with. Let g´ = g that I got from A. By A we have Loves(b, g). Hence Loves(b´, g´). A-To help: B-Test: A-Get help: B-Construct: A-Assure: B-Prove: I’m your advisory by testing with "objects. I prove B is true by constructing the $objects and proving the final statement. ‹#› 122 Jeff’s Informal Proofs A  B Prove $g, "b, Loves(b, g) A: "b´, $g´, Loves(b´, g´) B: Assume A Prove B by playing the game Let g be the girl assumed to exist in A. Let b´ be an arbitrary boy. Let b = b´ be the boy I need help with. Let g´ = g that I got from A. By A we have Loves(b, g). Hence Loves(b´, g´). A-To help: B-Test: A-Get help: B-Construct: A-Assure: B-Prove: I get help by giving you "objects. I assure A is true. To help I construct the $objects and assure the final statement. ‹#› 123 Jeff’s Informal Proofs ‹#› 124 Jeff’s Informal Proofs A computational problem is computable by a Java Program by a Turing Machine A  B Prove $ Java M, " ASCII I, $ time t, P(I)=M(I) & Time(M,I)=t A: $ TM M´, " binary I´, $ time t´, P(I´)=M´(I´) & Time(M´,I´)=t´ B: Assume A Prove B by playing the game ‹#› 125 Jeff’s Informal Proofs $ Java M, " ASCII I, $ time t, A: $ TM M´, " binary I´, $ time t´, P(I´)=M´(I´) & Time(M´,I´)=t´ B: A  B Prove Assume A Prove B by playing the game Let M´ be the TM compiled from the Java M assume in A. Let I´ be an arbitrary binary input. Let t´ be the time adjusted from time t assumed in A. P(I)=M(I) & Time(M,I)=t and hence P(I´)=M´(I´) & Time(M´,I´)=t´ I’m your advisory by testing with "objects. I prove B is true by constructing the $objects and proving the final statement. B-Construct: B-Test: B-Construct: Proving: ‹#› 126 Jeff’s Informal Proofs $ Java M, " ASCII I, $ time t, P(I)=M(I) & Time(M,I)=t A: $ TM M´, " binary I´, $ time t´, P(I´)=M´(I´) & Time(M´,I´)=t´ B: A  B Prove Assume A Prove B by playing the game Let M be the Java program assumed to exist in A. Let I be the input I need help with. Let t be the time A assumes exists for M and I. By A we have P(I)=M(I) & Time(M,I)=t I get help by giving you "objects. I assure A is true. To help I construct the $objects and assure the final statement. A-To help: A-Get help: A-To help: A-Assure: ‹#› 127 Jeff’s Informal Proofs $ Java M, " ASCII I, $ time t, P(I)=M(I) & Time(M,I)=t A: $ TM M´, " binary I´, $ time t´, P(I´)=M´(I´) & Time(M´,I´)=t´ B: A  B Prove Assume A Prove B by playing the game Let M be the Java program assumed to exist in A. Let M´ = CompileJAVATM (M). Let I´ be an arbitrary binary input. Let I = CompilebinaryASCII (I´). Let t be the time A assumes exists for M and I. Let t´ = CompileJAVATM time(t) P(I´) = P(I) (by CompilebinaryASCII) P(I) = M(I) (by A) M(I) = M´(I´) (by CompileJAVATM) P(I´)=M´(I´) (combine) Time(M´,I´)=t´ (similar) and CompileJAVATM and CompilebinaryASCII A-To help: B-Construct: B-Test: A-Get help: A-To help: B-Construct: D-Assure: A-Assure: C-Assure: B-Prove: B-Prove: ‹#› 128 Jeff’s Informal Proofs $ Java M, " ASCII I, $ time t, P(I)=M(I) & Time(M,I)=t A: $ TM M´, " binary I´, $ time t´, P(I´)=M´(I´) & Time(M´,I´)=t´ B: A  B Prove Assume A Prove B by playing the game Let M be the Java program assumed to exist in A. Let M´ = CompileJAVATM (M). Let I´ be an arbitrary binary input. Let I = CompilebinaryASCII (I´). Let t be the time A assumes exists for M and I. Let t´ = CompileJAVATM time(t) P(I)=M(I) P(I´)=M´(I´) and CompileJAVATM and CompilebinaryASCII A-To help: B-Construct: B-Test: A-Get help: A-To help: B-Construct: A-Assure: B-Prove: I’m your advisory by testing with "objects. I prove B is true by constructing the $objects and proving the final statement. ‹#› 129 Jeff’s Informal Proofs $ Java M, " ASCII I, $ time t, P(I)=M(I) & Time(M,I)=t A: $ TM M´, " binary I´, $ time t´, P(I´)=M´(I´) & Time(M´,I´)=t´ B: A  B Prove Assume A Prove B by playing the game Let M be the Java program assumed to exist in A. Let M´ = CompileJAVATM (M). Let I´ be an arbitrary binary input. Let I = CompilebinaryASCII (I´). Let t be the time A assumes exists for M and I. Let t´ = CompileJAVATM time(t) P(I)=M(I) P(I´)=M´(I´) and CompileJAVATM and CompilebinaryASCII A-To help: B-Construct: B-Test: A-Get help: A-To help: B-Construct: A-Assure: B-Prove: I get help by giving you "objects. I assure A is true. To help I construct the $objects and assure the final statement. ‹#› 130 Jeff’s Informal Proofs A  B Prove Assume A Prove B by playing the game and CompileJAVATM and CompilebinaryASCII $ Java M, " ASCII I, $ time t, P(I)=M(I) & Time(M,I)=t A: $ TM M´, " binary I´, $ time t´, P(I´)=M´(I´) & Time(M´,I´)=t´ B: ‹#› 131 Jeff’s Informal Proofs " Java M, $ TM M´, " binary I´, M´(I´)=M (I) I = CompilebinaryASCII (I´) C: Let M be the Java program I need help with. Let M´ be a TM constructed (compiled) from M. Let I´ be an arbitrary binary input I need help with. Let I = CompilebinaryASCII (I´). We assure M´(I´)=M (I) and CompileJAVATM and CompilebinaryASCII C-Get help: C-To help: C-Get help: D-To help: C-Assure: I get help by giving you "objects. I assure C is true. To help I construct the $objects and assure the final statement. ‹#› 132 Jeff’s Informal Proofs $ Java M, " ASCII I, $ time t, P(I)=M(I) & Time(M,I)=t A: $ TM M´, " binary I´, $ time t´, P(I´)=M´(I´) & Time(M´,I´)=t´ B: A&C&D  B Prove Assume A&C&D Prove B by playing the game Let M be the Java program assumed to exist in A. Let M´ = CompileJAVATM (M). Let I´ be an arbitrary binary input. Let I = CompilebinaryASCII (I´). Let t be the time A assumes exists for M and I. Let t´ = CompileJAVATM time(t) P(I)=M(I) P(I´)=M´(I´) A-To help: B-Construct: B-Test: A-Get help: A-To help: B-Construct: A-Assure: B-Prove: Let M be the Java program I need help with. Let M´ be a TM constructed (compiled) from M. Let I´ be an arbitrary binary input I need help with. Let I = CompilebinaryASCII (I´). P(I´) = P(I) M´(I´)=M (I) C-Get help: C-To help: C-Get help: D-To help: D-Assure: C-Assure: " Java M, $ TM M´, " binary I´, M´(I´)=M (I) I = CompilebinaryASCII (I´) C: ‹#› 133 Proofs with Implications 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 Proofs with Implications A computational problem is computable by a Java Program by a Turing Machine Why are these the same? Proofs with Implications 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 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: 166 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 167 A(I)=P(I) Upper Bound: The Time Complexity We need it to run in say n2 time. Time(A,I) £ n2 168 A(I)=P(I) Upper Bound: The Time Complexity But what is n? Time(A,I) £ Tupper(|I|) Time(A,I) £ n2 169 A(I)=P(I) Upper Bound: The Time Complexity Between these? Time(A,I) £ Tupper(|I|) and 170 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, 171 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, 172 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, 173 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? 174 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, 175 A(I)=P(I) Upper Bound: The Time Complexity How does the proof game go? Time(A,I) £ Tupper(|I|) and "I, $A, 176 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, 177 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: 178 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: 179 $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. 180 The Time Complexity How does the proof game go? "A, $I, [ A(I)  P(I) or Time(A,I) ³ Tlower(|I|)] Lower Bound: 181 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 . 182 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. 183 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, 184 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, 185 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, 186 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. 187 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, 188 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 189 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 inﬁnity. There are more than one inﬁnities 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 inﬁnity. 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 Trudeau Bob Sam Fred John Scheer Bob Sam Trudeau In both examples, every person loves a politician. The difference? One politician Could be a different politician 213 Understand Quantifiers!!! One politician Could be a different politician Fred Trudeau Bob Sam Fred John Scheer Bob Sam Trudeau “There is a politician whom everybody loves.” “For each voter, there is a politician.” Not clear. “There is a inverse (eg 1/3) for every reals.” “For each person, there is God.” 214 Understand Quantifiers!!! $politician, "voters, Loves(v, p) "voters, $politician, Loves(v, p) Fred Trudeau Bob Sam Fred John Scheer Bob Sam Trudeau One politician Could be a different politician 215 John “There is a politician that is loved by everyone.” This statement is “about” a politician. The existence of such a politician. We claim that this politician is “loved by everyone”. $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.” Understand Quantifiers!!! Fred Trudeau Bob Sam Fred John Scheer Bob Sam Trudeau 216 John “There is a politician that is loved by everyone.” This statement is “about” a politician. The existence of such a politician. We claim that this politician is “loved by everyone”. $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.” Understand Quantifiers!!! Fred Trudeau Bob Sam Fred John Scheer Bob Sam Trudeau 217 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) 218 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.” 219 $ $ " ³ £ £ c c n n n c g n f n c g n 1 2 0 0 1 2 , , , , ( ) ( ) ( )

Related Posts