Complexity & Chaos
Epstein Suite indexes the text; the original document lives at its official source. We don't host the original file — view it on the official release to read it in full.
View the original on the official releaseDocument text
Text is machine OCR and may contain errors. Confirm against the original source above.
Complexity & Chaos
running any algorithm can solve, and then
there are the free will problems: how do
we pick a problem in the first place? How
do inventors come up with problems no
one had ever thought to solve in the first
place, such as the invention of the Rubik’s
Cube?
169
Problem
Flat
nlogn
Linear
Logarithmic
Exponential
P
Near NP
NP-non-complete
NP-Complete, tractable
Chaotic
NP-Complete, Quantum
NP-Complete, intractable
PSPACE
Non-computable
Non-deterministic,
Non-time divisible, Non-
computable
Impossible
Known Unknowns
Unknown Unknowns
Erné Rubik's Cube
Example
Print File (for Human)
Searching a list
Finding the lowest number in a list
Long Multiplication
Long Division
Most Algorithms
Factor Prime Number
Perfect Game of Chess
Travelling Salesman, SAT
Weather
Modeling a Quantum Process
Busy Beaver, Towers of Hanoi
Graph Problems, Places Game
Creativity, Finding Fermat Theorem for a
Turing machine, Tiling the plane with Penrose
Triangles
Free will
Halting problem for a Turing Machine, some
mathematical theorems such as the Continuum
Hypothesis in ZF+AC (Hilberts Ist). Travelling
faster than the speed of light. Understanding
the American tax code.
I know that I don’t know either way.
I have not thought to ask that question yet.
Inventing the Rubik's Cube
HOUSE_OVERSIGHT_015859
Have a question about what this document contains?
Ask the documents