Analyse de complexité pour un théorème de Hall sur les fractions continues

&
Mathematical Logic Quarterly 42 (1):134-144 (1996)
  Copy   BIBTEX

Abstract

We give a polynomial time controlled version of a theorem of M. Hall: every real number can be written as the sum of two irrational numbers whose developments into a continued fraction contain only 1, 2, 3 or 4

Categories

Keywords

Reprint years

DOI

10.1002/malq.19960420112

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,867

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Complexity analysis for a Hall theorem on continuous fractions.S. Labhalla & H. Lombardi - 1996 - Mathematical Logic Quarterly 42 (1):134-144.
Real numbers, continued fractions and complexity classes.Salah Labhalla & Henri Lombardi - 1990 - Annals of Pure and Applied Logic 50 (1):1-28.
Every polynomial-time 1-degree collapses if and only if P = PSPACE.Stephen A. Fenner, Stuart A. Kurtz & James S. Royer - 2004 - Journal of Symbolic Logic 69 (3):713-741.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Light affine lambda calculus and polynomial time strong normalization.Kazushige Terui - 2007 - Archive for Mathematical Logic 46 (3-4):253-280.
Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.F. Stephan & B. Borchert - 2000 - Mathematical Logic Quarterly 46 (4):489-504.
Computability of Minimizers and Separating Hyperplanes.Kam-Chau Wong - 1996 - Mathematical Logic Quarterly 42 (1):564-568.
Some subrecursive versions of Grzegorczyk's Uniformity Theorem.Dimiter Skordev - 2004 - Mathematical Logic Quarterly 50 (4-5):520-524.
Continued fractions of primitive recursive real numbers.Ivan Georgiev - 2015 - Mathematical Logic Quarterly 61 (4-5):288-306.

Analytics

Added to PP
2013-12-01

Downloads
16 (#903,770)

6 months
8 (#506,113)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

No citations found.

Add more citations

References found in this work

Varieties of constructive mathematics.D. S. Bridges & Fred Richman - 1987 - New York: Cambridge University Press. Edited by Fred Richman.

Add more references