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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,199
Through your library

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.

Add more references

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.

Add more citations

Similar books and articles

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 )

How can I increase my downloads?

Downloads

My notes