Easy, Hard, Impossible
Download
Report
Transcript Easy, Hard, Impossible
Easy, Hard, and Impossible
Elaine Rich
Easy
Tic Tac Toe
Hard
Chess
The Turk
Unveiled in 1770.
Searching for the Best Move
A
B
E
(8)
F
(-6)
C
G
(0)
H
(0)
I
(2)
D
J
(5)
K
L
M
(-4) (10) (5)
How Much Computation Does it Take?
• Middle game branching factor 35
• Lookahead required to play master level chess 8
• 358
How Much Computation Does it Take?
• Middle game branching factor 35
• Lookahead required to play master level chess 8
• 358
• Seconds in a year
2,000,000,000,000
How Much Computation Does it Take?
• Middle game branching factor 35
• Lookahead required to play master level chess 8
• 358
• Seconds in a year
• Seconds since Big Bang
2,000,000,000,000
31,536,000
300,000,000,000,000,000
The Turk
Still fascinates people.
How Did It Work?
A Modern
Reconstruction
Built by John Gaughan. First
displayed in 1989. Controlled
by a computer. Uses the
Turk’s original chess board.
Chess Today
In 1997, Deep Blue beat Garry
Kasparov.
Seems Hard But Really Easy
Nim
At your turn, you must choose a pile, then remove as
many sticks from the pile as you like.
The player who takes the last stick(s) wins.
Nim
Now let’s try:
Nim
Now let’s try:
Oops, now there are a lot of possibilities to try.
Nim
http://www.gamedesign.jp/flash/nim/nim.html
Binary Numbers
16
8
4
2
1
1
0
1
1
1
0
0
1
1
0
0
0
0
1
0
1
1
1
0
5
9
21
3
16
Nim
My turn:
10
10
11
11
(2)
(2)
(3)
To form the last row: XOR each column.
XOR: if number of 1’s is even:
if number of 1’s is odd:
0
1
Nim
My turn:
10
10
11
11
For the current player:
• Guaranteed loss if last row is all 0’s.
• Guaranteed win otherwise.
(2)
(2)
(3)
Nim
My turn:
100
010
101
011
For the current player:
• Guaranteed loss if last row is all 0’s.
• Guaranteed win otherwise.
(4)
(2)
(5)
Nim
Your turn:
100
001
101
000
For the current player:
• Guaranteed loss if last row is all 0’s.
• Guaranteed win otherwise.
(4)
(1)
(5)
Following Paths
Seven Bridges of Königsberg
Seven Bridges of Königsberg
Seven Bridges of Königsberg:
1
3
4
2
Seven Bridges of Königsberg
Seven Bridges of Königsberg:
1
3
4
2
As a graph:
Eulerian Paths and Circuits
Cross every edge exactly once.
Leonhard Euler
1707 - 1783
Eulerian Paths and Circuits
Cross every edge exactly once.
Leonhard Euler
1707 - 1783
There is a circuit if every node
touches an even number of edges.
So, Can We Do It?
1
3
4
2
As a graph:
Unfortuntately, There Isn’t Always a Trick
Suppose we need to visit every node exactly once.
The Traveling Salesman Problem
15
25
10
28
20
4
8
40
9
7
3
23
Find the shortest circuit that visits every city exactly once.
Visting Nodes Rather Than Edges
● A Hamiltonian path: visit every node exactly once.
● A Hamiltonian circuit: visit every node exactly once
and end up where you started.
All these people care:
• Salesmen,
• Farm inspectors,
• Network analysts
The Traveling Salesman Problem
15
25
10
28
20
4
8
40
9
7
3
23
Given n cities:
Choose a first city
Choose a second
Choose a third
…
n
n-1
n-2
n!
The Traveling Salesman Problem
Can we do better than n!
● First
city doesn’t matter.
● Order doesn’t matter.
So we get (n-1!)/2.
The Growth Rate of n!
2
2
11
479001600
3
6
12
6227020800
4
24
13
87178291200
5
120
14
1307674368000
6
720
15
20922789888000
7
5040
16
355687428096000
8
40320
17
6402373705728000
9
362880
18
121645100408832000
10
3628800
19
2432902008176640000
11
39916800
36
3.61041
Putting it into Perspective
Speed of light
Width of a proton
At one operation in the
time it takes light to
cross a proton
Since Big Bang
Ops since Big Bang
Neurons in brain
Parallel ops since Big
Bang
3108 m/sec
10-15 m
31023 ops/sec
31017 sec
91040 ops
1011
91051
36! = 3.61041
43! = 61052
Is This The Best We Can Do?
Probably.
Would you like to win $1M?
The Millenium Prize
Impossible
An Interesting Puzzle
List 1
1
2
3
b
babbb
ba
4
bbbaa
2
List 1
babbb
List 2
ba
List 2
bbb
ba
a
babbb
An Interesting Puzzle
List 1
1
2
3
b
babbb
ba
4
bbbaa
2
1
List 1
babbbb
List 2
babbb
List 2
bbb
ba
a
babbb
An Interesting Puzzle
List 1
1
2
3
b
babbb
ba
4
bbbaa
2
1
List 2
bbb
ba
a
babbb
1
List 1
babbbbb
List 2
babbbbbb
An Interesting Puzzle
List 1
1
2
3
b
babbb
ba
4
bbbaa
2
1
List 2
bbb
ba
a
babbb
1 3
List 1
babbbbbba
List 2
babbbbbba
The Post Correspondence Problem
List 1
List 2
1
11
011
2
01
0
3
001
110
The Post Correspondence Problem
List 1
1
2
3
ab
ab
aa
List 2
a
ba
baa
The Post Correspondence Problem
List 1
1
2
3
1101
0110
1
List 2
1
11
110
Can A Program Do This?
Can we write a program to answer the following
question:
Given a PCP problem, decide whether or
not it has a solution. Return:
True if it does.
False if it does not.
The Post Correspondence Problem
A program to solve this problem:
Until a solution or a dead end is found do:
If dead end, halt and report no.
Generate the next candidate solution.
Test it. If it is a solution, halt and report yes.
So, if there are say 4 rows in the table, we’ll try:
1
2
3
4
1,1
1,2
1,3
1,4
2,1 ……
1,1,1 ….
1,5
Will This Work?
• If there is a solution:
• If there is no solution:
Programs Debug Programs
Given an arbitrary program, can it be guaranteed to halt?
read name
if name = “Elaine”
then print “You win!!”
else print “You lose ”
Programs Debug Programs
Given an arbitrary program, can it be guaranteed to halt?
The 3x + 1 Problem
read number
until number = 1 do
if number is even then: number number/2
if number is odd then: number 3 number + 1
Suppose number is 7:
Programs Debug Programs
Given an arbitrary program, can it be guaranteed to halt?
read number
until number = 1 do
if number is even then: number number/2
if number is odd then: number 3 number + 1
Collatz Conjecture: This program always halts.
We can try it on big numbers:
http://www.nitrxgen.net/collatz/7865765/
The Impossible
The halting problem cannot be solved.
We can prove that no program can ever be written that
can look at arbitrary other programs and decide whether
or not they always halt.
Other Unsolvable Problems
PCP:
• We can encode a <program>,<input> pair as an
instance of PCP so that the PCP problem has a
solution iff <program> halts on <input>.
2
1
1
List 1
babbbbb
List 2
babbbbbb
• So if PCP were solvable then Halting would be.
• But Halting isn’t. So neither is PCP.
Which is Amazing
Given the things programs can do.
http://www.youtube.com/watch?v=WFR3lOm_xhE
Which is Amazing
Given the things programs can do.
http://www.google.com/selfdrivingcar/