Infinite Versions of Some Problems from Finite Complexity Theory

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
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 29,567
External links

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
References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles
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.
Varieties of Finitism.Manuel Bremer - 2007 - Metaphysica 8 (2):131-148.
Hegel's True Infinity As Panentheism.Robert R. Williams - 2010 - The Owl of Minerva 42 (1-2):137-152.
Added to PP index
2010-08-24

Total downloads
5 ( #607,189 of 2,180,803 )

Recent downloads (6 months)
1 ( #299,591 of 2,180,803 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums