Hostname: page-component-cd9895bd7-jkksz Total loading time: 0 Render date: 2024-12-23T13:26:03.988Z Has data issue: false hasContentIssue false
  • English
  • Français

A Combinatorial Approach to Complexity Theory via Ordinal Hierarchies

Published online by Cambridge University Press:  12 September 2008

Walter A. Deuber  and
Wolfgang Thumser
Walter A. Deuber
Affiliation:
University of Bielefeld, Faukultät Mathematik, Postfach 10 01 31 33501 Bielefeld 1, Germany
Wolfgang Thumser
Affiliation:
University of Bielefeld, Faukultät Mathematik, Postfach 10 01 31 33501 Bielefeld 1, Germany
Get access Rights & Permissions [Opens in a new window]

Abstract

Long regressive sequences in well-quasi-ordered sets contain ascendingsubsequences of length n. The complexity of the corresponding function H(n) is studied in the Grzegorczyk-Wainer hierarchy. An extension to regressive canonical colourings is indicated.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 2 , June 1994 , pp. 177 - 190
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Erdőos, P., Hainal, A., Máté, A. and Rado, R. (1984) Combinatorial set theory: Partition relations for cardinals. Studies in Logic and the Foundations of Mathematics 106, North-Holland.Google Scholar
[2]Erdos, P. and Mills, G. (1981) Some Bounds for the Ramsey-Harrington Numbers. J. of Comb. Theory, Ser. A 30, 53–70.CrossRefGoogle Scholar
[3]Erdős, R. and Rado, R. (1950) A combinatorial Theorem. Journal of the London Mathematical Society 25, 249–255.CrossRefGoogle Scholar
[4]Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Composito Math. 2, 464–470.Google Scholar
[5]Gentzen, G. (1936) Die Widerspruchsfreiheit der reinen Zahlentheorie. Mathematische Annalen 112, 493–565.CrossRefGoogle Scholar
[6]Gordan's, P. (1885) Vorlesungen über Invariantentheorie, Hrsg. v. Geo. Kerschensteiner. 1. Bd. Determinanten (XI, 201S.). Teubner, Leibzig.Google Scholar
[7]Gödel, K. (1931) Uber formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatschefte fur Mathematik und Physik 38, 173–198.CrossRefGoogle Scholar
[8]Grzegorczyk, A. (1933) Some classes of recursive functions. Rozprawy matematiczne 4, Instytut Matematyczny Polskiej Akademie Nauk, Warsaw.Google Scholar
[9]Graham, R., Rothschild, B. and Spencer, J. (1990) Ramsey theory, Wiley, New York.Google Scholar
[10]Harzheim, E. (1967) Eine kombinatorische Frage zahlentheoretischer Art. Publicationes Mathematicae Debrecen 14, 45–51.CrossRefGoogle Scholar
[11]Harzheim, E. (1982) Combinatorial theorems on contractive mappings in power sets. Discrete math. 40, 193–201.CrossRefGoogle Scholar
[12]Higman, G. (1952) Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 2, 326–336.CrossRefGoogle Scholar
[13]Jullien, P. (1968) Analyse combinatoire – Sur un théorème d'extension dans la théorie des mots. C.R. Acad. Sci. Paris, Ser. A 266, 851–854.Google Scholar
[14]Kanamori, A. and McAloon, K. (1987) On Gödel incompleteness and finite combinatorics. Annals of Pure and Applied Logic 33, 23–41.CrossRefGoogle Scholar
[15]Kreisel, G. (1952) On the interpretation of nonfinitistic proofs. Journal of Symbolic Logic 17, II, 43–58.CrossRefGoogle Scholar
[16]Kruskal, J. B. (1972) The Theory of Well-Quasi-Ordering: A Frequently Discovered Concept. Journal of Combinatorial Theory (A) 13, 297–305.CrossRefGoogle Scholar
[17]Leeb, K. (1973) Vorlesungen über Pascaltheorie. Arbeitsbericht des Instituts für mathematische Maschinen und Datenverarbeitung, Friedrich Alexander Universität Erlangen Nürnberg, Bd. 6 Nr. 7.Google Scholar
[18]Leeb, K. Personal communications.Google Scholar
[19]Loebl, M. and Nešsetfil, J. (1991) Unprovable combinatorial statements. In: Keedwell, A. D.(ed.) Surveys in Combinatorics.CrossRefGoogle Scholar
[20]Mills, G. (1980) A tree analysis of unprovable combinatorial statements. Model theory of Algebra and Arithmetic. Springer-Verlag Lecture Notes in Mathematics 834, 248–311.CrossRefGoogle Scholar
[21]Nešsetřil, J. and Rödl, V. (1990) Mathematics of Ramsey Theory, Springer-Verlag, Berlin, Heidelberg.CrossRefGoogle Scholar
[22]Paris, J. and Harrington, L. (1977) A mathematical incompleteness in Peano Arithmetic. Handbook of Mathematical Logic. In: Barwise, J. (ed.) North-Holland Publishing Company, 1133–1142.CrossRefGoogle Scholar
[23]Prömel, H. J., Thumser, W. and Voigt, B. (1989) Fast growing functions based on Ramsey theorems. Forschungsinstitut fur Diskrete Mathematik, Bonn (preprint).Google Scholar
[24]Prömel, H. J., Thumser, W. and Voigt, B. (1991) Fast growing functions based on Ramsey theorems. Discrete Mathematics 95, 341–358.CrossRefGoogle Scholar
[25]Prömel, H. J. and Voigt, B. (1989) Aspects of Ramsey Theory I: Sets, Report number 87495-OR, Forschungsinstitut fur Diskrete Mathematik, Universität Bonn, Germany.Google Scholar
[26]Prömel, H. J. and Voigt, B. (1993) Aspects of Ramsey Theory, Springer Verlag, Berlin.Google Scholar
[27]Ramsey, F. P. (1930) On a problem of formal logic. Proceedings of the London Mathematical Society 30, 264–286.CrossRefGoogle Scholar
[28]Simpson, S. G. (1987) Unprovable theorems and fast growing functions. In: Simpson, S. G. (ed.) Logic and Combinatorics. Contemporary Mathematics 65, 359–394.CrossRefGoogle Scholar
[29]Thumser, W. (1989) On upper Bounds for Kanamori McAloon Function, preprint 89–10, Sonderforschungsbereich 343 “Diskrete Strukturen in der Mathematik”, Universität Bielefeld.Google Scholar
[30]Thumser, W. (1992) On the well-order type of certain combinatorial structures, Bielefeld (manuscript, submitted).Google Scholar
[31]Wainer, S. S. (1972) Ordinal recursion and a refinement of the extended Grzegorczyk hierarchy. Journal of Symbolic Logic 37 281–292.CrossRefGoogle Scholar