Some decision problems of enormous complexity

Abstract

We present some new decision and comparison problems of unusually high computational complexity. Most of the problems are strictly combinatorial in nature; others involve basic logical notions. Their complexities range from iterated exponential time completeness to (0 time completeness to ((((,0) time completeness to ((((,,0) time completeness. These three ordinals are well known ordinals from proof theory, and their associated com- plexity classes represent new levels of computational complexity for natural decision problems. Proofs will appear in an extended version of this manuscript to be published elsewhere.

Categories

Keywords

Reprint years

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,830

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

  • Only published works are available at libraries.

My notes

Similar books and articles

Logic and Complexity.Richard Lassaigne & Michel de Rougemont - 2012 - Springer Verlag.
AI-Completeness: Using Deep Learning to Eliminate the Human Factor.Kristina Šekrst - 2020 - In Sandro Skansi (ed.), Guide to Deep Learning Basics. Springer. pp. 117-130.
Complexity of intuitionistic propositional logic and its fragments.Mikhail Rybakov - 2008 - Journal of Applied Non-Classical Logics 18 (2):267-292.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Complexity.Alasdair Urquhart - 2003 - In Luciano Floridi (ed.), The Blackwell guide to the philosophy of computing and information. Blackwell. pp. 18–27.
Tractability and the computational mind.Rineke Verbrugge & Jakub Szymanik - 2018 - In Mark Sprevak & Matteo Colombo (eds.), The Routledge Handbook of the Computational Mind. Routledge. pp. 339-353.
On The Computational Consequences of Independence in Propositional Logic.Merlijn Sevenster - 2006 - Synthese 149 (2):257-283.
Complexity of interpolation and related problems in positive calculi.Larisa Maksimova - 2002 - Journal of Symbolic Logic 67 (1):397-408.
A Hierarchical Completeness Proof for Propositional Interval Temporal Logic with Finite Time.Ben Moszkowski - 2004 - Journal of Applied Non-Classical Logics 14 (1-2):55-104.
Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.

Analytics

Added to PP
2009-01-28

Downloads
107 (#197,669)

6 months
107 (#55,436)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references