Published: 3rd June 2010
DOI: 10.4204/EPTCS.24
ISSN: 2075-2180

EPTCS 24

Proceedings Seventh International Conference on
Computability and Complexity in Analysis
Zhenjiang, China, 21-25th June 2010

Edited by: Xizhong Zheng and Ning Zhong

Preface Xizhong Zheng and Ning Zhong
Invited Presentation: Nontriviality and Strong Nontriviality for Exponential Time Klaus Ambos-Spies	1
Invited Presentation: Polynomial-time computability in analysis: a survey Ker-I Ko	2
Invited Presentation: Computational Complexity in Analysis Robert Rettinger	3
Invited Presentation: Computable Measure Theory Klaus Weihrauch	4
Invited Presentation: The monotone completeness theorem in constructive reverse mathematics Hajime Ishihara	5
Invited Presentation: Computing the speed of convergence of ergodic averages and pseudorandom points in computable dynamical systems Stefano Galatolo, Mathieu Hoyrup and Cristóbal Rojas	7
A domain-theoretic investigation of posets of sub-sigma-algebras (extended abstract) Ingo Battenfeld	19
On the Weak Computability of Continuous Real Functions Matthew S. Bauer and Xizhong Zheng	29
Computation with Advice Vasco Brattka and Arno Pauly	41
The Cardinality of an Oracle in Blum-Shub-Smale Computation Wesley Calvert, Ken Kramer and Russell Miller	56
Effective Capacity and Randomness of Closed Sets Douglas Cenzer and Paul Brodhead	67
Real Analytic Machines and Degrees Tobias Gärtner and Martin Ziegler	77
The descriptive set-theoretic complexity of the set of points of continuity of a multi-valued function (Extended Abstract) Vassilios Gregoriades	92
Computing the Solutions of the Combined Korteweg-de Vries Equation by Turing Machines Dianchen Lu, Qingyan Wang and Rui Zheng	101
Making big steps in trajectories Norbert Th. Müller and Margarita Korovina	106
A Local to Global Principle for the Complexity of Riemann Mappings (Extended Abstract) Robert Rettinger	120
NP-Logic Systems and Model-Equivalence Reductions Yuping Shen and Xishun Zhao	130
Computational Complexity of Iterated Maps on the Interval (Extended Abstract) Christoph Spandl	139
A Rigorous Extension of the Schönhage-Strassen Integer Multiplication Algorithm Using Complex Interval Arithmetic Thomas Steinke and Raazesh Sainudiin	151
Complete Multi-Representations of Sets in a Computable Measure Space Yongcheng Wu	160

Preface

This volume of the Electronic Proceedings in Theoretical Computer Science (EPTCS) contains abstracts/extended abstracts of talks to be presented at the Seventh International Conference on Computability and Complexity in Analysis (CCA) that will take place in Zhenjiang, China, June 21-25, 2010. This conference is the seventeenth event in the series of CCA annual meetings. The CCA conferences are aimed at promoting the study and advancement of the theory of computability and complexity over real-valued data and its application.

We thank authors for their contributions to this EPTCS volume and members of the CCA2010 Program Committee (see below) and external reviewers for their help. We also thank Professor Rob van Glabbeek, the editor-in-chief of EPTCS, for his support and the local organizers (see below) for all their help with the organization of CCA2010. The CCA 2010 is co-sponsored by Arcadia University, Guizhou University, Jiangsu University, Nanjing University, Peking University, and Sun Yat-Sen University.

CCA 2010 Program Committee:

Andrej Bauer (Ljubljana, Slovenia)
Douglas Bridges (Canterbury, New Zealand)
Vasco Brattka (Cape Town, South Africa)
Douglas Cenzer (Gainesville, USA)
Martin Escardo (Birmingham, UK)
Peter Gacs (Boston, USA)
Daniel Graca (Faro, Portugal)
Vladik Kreinovich (El Paso, USA)
Angsheng Li (Beijing, China)
Elvira Mayordomo (Zaragoza, Spain)
Matthias Schroeder (Munich, Germany)
Dieter Spreen (Siegen, Germany)
Kaile Su (Beijing, China)
Hideki Tsuiki (Kyoto, Japan)
Xizhong Zheng, co-chair (Zhenjiang, China and Glenside, USA)
Ning Zhong, co-chair (Cincinnati, USA)
Martin Ziegler (Darmstadt, Germany)

CCA2010 Local Organizing Committee:

Kejin Bao (Zhenjiang, China)
Decheng Ding, co-chair (Nanjing, China)
Hongxing Yao (Zhenjiang, China)
Dianchen Lu, co-chair (Zhenjiang, China)
Daoyun Xu (Guiyang, China)
Xishun Zhao (Guangzhou, China)
Xizhong Zheng, co-chair (Zhenjiang, China and Glenside, USA)

Xizhong Zheng and Ning Zhong
Program Committee Co-Chairs
Glenside and Cincinnati, May 2010

Nontriviality and Strong Nontriviality for Exponential Time

Klaus Ambos-Spies

Following Lutz (1995) we consider a problem to be weakly hard for a complexity class C if a nonnegligible part of the problems in C can be reduced to C. For the exponential-time class E (the union of DTIME(2^{kn}) for all k) Lutz formalized this concept by introducing a resource-bounded measure on this class and by saying that a subclass of E is negligible if it has measure 0 in E. In our talk we introduce and discuss some new weak hardness notions for E, called E-nontriviality and strong E-nontriviality, which generalize Lutz's weak hardness notion for E and which are conceptually much simpler than Lutz's concept. Here a set A is E-nontrivial if the problems in E which can be reduced to A are not contained in a single level DTIME(2^{kn}) of the hierarchy E, and A is strongly E-nontrivial if, for any number k there is a problem in E which can be reduced to A and which is almost-everywhere 2^{kn}-complex (i.e., bi-immune for the k-th level DTIME(2^{kn}) of the hierarchy E). This work is joint work with Timur Bakibayev.

Polynomial-time computability in analysis: a survey

Ker-I Ko

This talk will present a brief survey of the complexity of real functions, including: computational models for real-valued computation, complexity hierarchy of basic numerical operations, computational complexity of differential and integral equations, and applications to computational geometry and complex analysis.

Computational Complexity in Analysis

Robert Rettinger

Whereas computational complexity is well established on discrete structures, it is only very rudimentary treated in Type-2-theory of effectivity. The aim of this talk is to shed some (subjectiv) light on a few aspects of computational complexity and some recent developments in this field. Problems we will consider are among others:

what is a good machine model to investigate complexity on type-2-objects?
how can we translate classes which are well known on discrete structures to the framework of Type-2-theory of effectivity, including nondeterministic, probabilistic and relativized classes?
natural representations and complexity
local and global complexity
separation of topological and computational aspects of complexity
scientific computation and complexity.

Computable Measure Theory

Klaus Weihrauch

Measure theory is a fundament of modern analysis. Computable measure theory studies those functions from measure theory which are computable. Compared to the immense number of publications in measure theory and the increasing number of publications in computable analysis there are still very few articles on computable measure theory. In the talk we introduce and discuss some basic concepts of computable measure theory. Furthermore, we present some of the results obtained so far. As in computable analysis numerous new results are waiting for becoming detected. The talk is considered as an invitation to study computable measure theory.

The monotone completeness theorem in constructive reverse mathematics

Hajime Ishihara (Japan Advanced Institute of Science and Technology)

In classical reverse mathematics, the monotone completeness theorem:

MCT: Every bounded monotone sequence of real numbers converges

is equivalent, over the subsystem RCA₀ of second order arithmetic, to the arithmetical comprehension axiom (ACA):

∃X ∀n (n∈X ↔ φ(n))

where φ is any arithmetical formula in which X does not occur freely; [8, Theorem III.2.2]. On the other hand, in Bishop's constructive mathematics [1–4], Mandelkarn [7] had shown that MCT is equivalent to the limited principle of omniscience (LPO or Σ⁰₁-PEM) which is an instance of the principle of excluded middle (PEM):

∃n (α(n) ≠ 0) ∨ ¬∃n (α(n) ≠ 0).

It has been noticed that most mathematical theorems equivalent to ACA in classical reverse mathematics are equivalent to LPO in constructive mathematics. Of course, there are exceptions. Although, in classical reverse mathematics, the Cauchy completeness of the reals:

CCR: Every Cauchy sequence of real numbers converges

is classified into ACA, it is provable in Bishop's constructive mathematics [1, Chapter 2, Theorem 2], [2, Theorem 3.3.3]. The reason is that, in classical reverse mathematics, using classical logic in which nonconstructive logical principles such as Σ⁰₁-PEM are provable, we have been focusing only on set (function) existence axioms but not on nonconstructive logical principles, whereas, in Bishop's constructive mathematics, assuming function existence axioms such as countable choice and dependent choice, we have been focusing only on nonconstructive logical principles but not on set (function) existence axioms.

In this talk, we investigate the monotone completeness theorem (MCT) within a framework of constructive reverse mathematics aiming at classifying various theorems in intuitionistic, constructive recursive and classical mathematics by logical principles, function existence axioms and their combinations [5]; see also [6,10]. We distinguish a Cauchy sequence with modulus from a Cauchy sequence without modulus, and we say that a sequence (x_n)_n of real numbers is a Cauchy sequence if there exists γ such that

∀k ∀m,n ≥ γ(k) (| x_m − x_n | < 2^−k) ;

a weak Cauchy sequence if

∀k ∃N ∀m,n ≥ N (| x_m − x_n | < 2^−k).

Note that, in classical reverse mathematics, CCR for weak Cauchy sequences is equivalent to ACA [8, Theorem III.2.2], and, in constructive mathematics, CCR for Cauchy sequences is provable without assuming countable choice [9, Theorem 5.4.2] (its proof is easily translated into a proof in RCA₀).

We give a logical principle Σ⁰₁-PEM⁺ which is stronger than Σ⁰₁-PEM, and show that Σ⁰₁-PEM⁺ is equivalent to the statement:

(1) Every bounded monotone sequence of real numbers is a weak Cauchy sequence.

Therefore the statement is a logical statement which is provable with classical logic without any function existence axiom. We also give a function existence axiom Π⁰₁-AC₀₀⁻ which is weaker than the axiom Π⁰₁-AC₀₀ of number-number choice for Π⁰₁-formulas, and show that Π⁰₁-AC₀₀⁻ is equivalent to the statement:

(2) Every weak Cauchy sequence of real numbers is a Cauchy sequence.

Hence the statement is a function existence statement which is provable in constructive mathematics with countable choice. Thus MCT is divided into the logical statement (1), the function existence statement (2), and CCR which is constructively provable without countable choice and also provable in RCA₀.

References

[1]	Errett Bishop, Foundations of Constructive Mathematics, McGraw-Hill, New York, 1967.
[2]	Errett Bishop and Douglas Bridges, Constructive Analysis, Springer, Berlin, 1985.
[3]	Douglas Bridges and Fred Richman, Varieties of Constructive Mathematics, London Math. Soc. Lecture Notes 97, Cambridge Univ. Press, London, 1987.
[4]	Douglas Bridges and Luminiţa Vîţa, Techniques of Constructive Analysis, Springer, New York, 2006.
[5]	Hajime Ishihara, Constructive reverse mathematics: compactness properties, In: L. Crosilla and P. Schuster eds., From Sets and Types to Analysis and Topology, Oxford Logic Guides 48, Oxford Univ. Press, 2005, 245-267.
[6]	Iris Loeb, Equivalents of the (weak) fan theorem, Ann. Pure Appl. Logic 132 (2005), 51-66.
[7]	Mark Mandelkern, Limited omniscience and the Bolzano-Weierstrass principle, Bull. London Math. Soc. 20 (1988), 319-320.
[8]	Stephen G. Simpson, Subsystems of Second Order Arithmetic, Springer, Berlin, 1999.
[9]	Anne S. Troelstra and Dirk van Dalen, Constructivism in Mathematics, Vol.I and II, North-Holland, Amsterdam, 1988.
[10]	Wim Veldman, Brouwer's fan theorem as an axiom and as a contrast to Kleene's alternative, preprint, Radboud University, Nijmegen, 2005.