Notre Dame Journal of Formal Logic 37 (4):545-553 (1996)
| 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
|
| Keywords | No keywords specified (fix it) |
| Categories | (categorize this paper) |
| DOI | 10.1305/ndjfl/1040046141 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
PhilArchive copy
Upload a copy of this paper Check publisher's policy Papers currently archived: 71,199
External links
- From the Publisher via CrossRef (no proxy)
- projecteuclid.org
(no proxy) - projecteuclid.org [2] (no proxy)
- projecteuclid.org [3] (no proxy)
- projecteuclid.org [4] (no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
- Sign in / register and customize your OpenURL resolver..
- Configure custom resolver
References found in this work BETA
Countable Algebra and Set Existence Axioms.Harvey M. Friedman - 1983 - Annals of Pure and Applied Logic 25 (2):141.
Which Set Existence Axioms Are Needed to Prove the Cauchy/Peano Theorem for Ordinary Differential Equations?Stephen G. Simpson - 1984 - Journal of Symbolic Logic 49 (3):783-802.
On the Complexity of Finding the Chromatic Number of a Recursive Graph I: The Bounded Case.Richard Beigel & William I. Gasarch - 1989 - Annals of Pure and Applied Logic 45 (1):1-38.
Reducibility Among Combinatorial Problems.Richard M. Karp, Raymond E. Miller & James W. Thatcher - 1975 - Journal of Symbolic Logic 40 (4):618-619.
Citations of this work BETA
Domatic Partitions of Computable Graphs.Matthew Jura, Oscar Levin & Tyler Markkanen - 2014 - Archive for Mathematical Logic 53 (1-2):137-155.
Similar books and articles
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.
Two Variable First-Order Logic Over Ordered Domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
On the Production of Subjectivity: Five Diagrams of the Finite-Infinite Relation.Simon O'Sullivan - 2012 - Palgrave-Macmillan.
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.
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 index
2010-08-24
Total views
16 ( #668,374 of 2,517,904 )
Recent downloads (6 months)
1 ( #409,045 of 2,517,904 )
2010-08-24
Total views
16 ( #668,374 of 2,517,904 )
Recent downloads (6 months)
1 ( #409,045 of 2,517,904 )
How can I increase my downloads?
Downloads
