Infinite Versions of Some Problems from Finite Complexity Theory

&
Notre Dame Journal of Formal Logic 37 (4):545-553 (1996)
  Copy   BIBTEX

Abstract

Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways

Categories

Keywords

Reprint years

DOI

10.1305/ndjfl/1040046141

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,164

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

Finite Model Theory.Heinz-Dieter Ebbinghaus & Jörg Flum - 2005 - Springer.
More undecidable lattices of Steinitz exchange systems.L. R. Galminas & John W. Rosenthal - 2002 - Journal of Symbolic Logic 67 (2):859-878.
A new applied approach for executing computations with infinite and infinitesimal quantities.Yaroslav D. Sergeyev - 2008 - Informatica 19 (4):567-596.
Elements of Finite Model Theory.Leonid Libkin - 2004 - Springer.
Infinite Ethics.Infinite Ethics - unknown
Infinite numbers are large finite numbers.Jeremy Gwiazda - unknown
Two variable first-order logic over ordered domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
On Infinite Number and Distance.Jeremy Gwiazda - 2012 - Constructivist Foundations 7 (2):126-130.
Finite mathematics.Shaughan Lavine - 1995 - Synthese 103 (3):389 - 420.
On the production of subjectivity: five diagrams of the finite-infinite relation.Simon O'Sullivan - 2012 - New York: Palgrave-Macmillan.
Varieties of Finitism.Manuel Bremer - 2007 - Metaphysica 8 (2):131-148.
Finite Model Theory and its Applications.Erich Grädel, Phokion Kolaitis, Libkin G., Marx Leonid, Spencer Maarten, Vardi Joel, Y. Moshe, Yde Venema & Scott Weinstein - 2007 - Springer.
Complexity and sustainability.Jennifer Wells - 2013 - New York: Routledge.
The Finite and the Infinite in Frege's Grundgesetze der Arithmetik.Richard Heck - 1998 - In Matthias Schirn (ed.), Philosophy of Mathematics Today. Oxford University Press.

Analytics

Added to PP
2010-08-24

Downloads
21 (#692,524)

6 months
4 (#678,769)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Domatic partitions of computable graphs.Matthew Jura, Oscar Levin & Tyler Markkanen - 2014 - Archive for Mathematical Logic 53 (1-2):137-155.

Add more citations

References found in this work

Countable algebra and set existence axioms.Harvey M. Friedman - 1983 - Annals of Pure and Applied Logic 25 (2):141.

Add more references