Computability, Complexity, and Practice of Real Computation
Tutorial at the University of Tokyo, Jan.30 to Feb.1 (2018)
This short lecture conveys the conceptional background to contemporary computational approaches in Engineering:
Synopsis:
Recap on discrete computability
Halting Problem
un/semi/decidability/enumerability
reduction
WHILE programs
Real Computability Theory
real numbers: binary vs. approximate
quality, real sequences and limits
computing real functions, Weierstrass
comput.cost, compactness, continuity
real arithmetic, join, maximum, integral
root finding: uncomputable argmax
uncomputable derivative/wave equation
non-extensionality, discrete enrichment
Recap on discrete complexity theory
Asymptotic algorithmic cost
Complexity classes P, NP, PSPACE, EXP
Polynomial-time reductions
Cook-Levin Theorem
Real Complexity Theory
Polynomial-time reals
Real functions and uniform complexity
Information-theoretic lower bounds
(Smooth) maximization ⇔ NP
Exact Real Computation
semantics: partial
>
,
choose()
Example algorithms: integer rounding, trisection
iRRAM
Schedule (with links to slides):
Komaba Campus, Building #15, Room #106
Tuesday (Jan.30) to Thursday (Feb.1), 2018
Tue 16:50-18:35
Wed 10:25-12:10
Wed 14:55-16:40
Thu 13:00-14:45
Thu 16:50-18:35
Slides
with
animations (proprietary PowerPoint)
Assignments:
Write WHILE programs for
binary predicate x>y
unary predicate odd(x)
binary multiplication (x,y)→x×y
Bonus if all three run in time O(log
x
).
For
WHILE
programs refer, e.g., to [Enderton'11,§1.2.3]
Prove that Specker's sequence is computable, but its limit is not:
where
t
(
m
) := #steps the WHILE program with code
m
makes on input
m
.
Let
a
∈(0;1) be computable,
f
:[0;a]→
R
computable, and
g
:[a;1]→
R
computable with
f
(
a
)=
g
(
a
).
Prove that their join
f
⊔
g
:[0;1]→
R
is again computable.
Let
h
:[0;1]→
R
be polynomial-time computable. Suppose P=NP.
Conclude that the real number max{
h
(
t
):
t
} is again polynomial-time computable.
Bonus: Conclude that
H
:[0;1]∋
x
→max{
h
(
t
):
t
≤
x
} is again polynomial-time computable.
install
iRRAM
on your (Linux) computer, compile and run the included example programs
Administration:
Host:
Akitoshi Kawamura
Instructor:
Martin Ziegler
Language:
English
Selected References:
Klaus Weihrauch:
Computable Analysis: An Introduction
, Springer (2000).
Ker-I Ko:
Complexity Theory of Real Functions
, Birkhäuser (1991).
Mark Braverman, Stephen Cook:
Computing over the Reals: Foundations for Scientific Computing
, Notices of the AMS (2006).
Akitoshi Kawamura, Stephen Cook:
Complexity Theory for Operators in Analysis
, ACM Transactions on Computation Theory
4
(2012).
Akitoshi Kawamura, Hiroyuki Ota, Carsten Rösnick, Martin Ziegler:
Computational Complexity of Smooth Differential Equations
, Logical Methods in Computer Science (2014).
Akitoshi Kawamura, Norbert Müller, Carsten Rösnick, Martin Ziegler:
Computational Benefit of Smoothness: Parameterized Bit-Complexity of Numerical Operators on Analytic Functions and Gevrey's Hierarchy
, pp.689-714 in the Journal of Complexity vol.
31:5
(2015).
Akitoshi Kawamura, Florian Steinberg, Martin Ziegler:
On the Computational Complexity of the Dirichlet Problem for Poisson's Equation
, pp.1437-1465 in
Mathematical Structures in Computer Science
vol.
27:8
(2017).
A. Kawamura
, M. Ziegler:
"Invitation to Real Complexity Theory: Algorithmic Foundations to Reliable Numerics with Bit-Costs"
,
18th Korea-Japan Joint Workshop on Algorithms and Computation
(2015).
Papadimitriou: Computational Complexity, Addison Wesley (1993)
Moore, Mertens:
The Nature of Computation
(2011)
Lewis, Papadimitrou: Elements of the Theory of Computation (2nd. ed.), Prentice-Hall (1997).
Arora, Barak: Computational Complexity - A Modern Approach, Cambridge University Press (2009).
Sipser: Introduction to the Theory of Computation, PWS Publishing (1997).
Herbert B. Enderton: Computability Theory, Academic Press (2011).