- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
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 waysOther Versions
No versions found
Links
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
Incompleteness in the Finite Domain.Pavel Pudlák - 2017 - Bulletin of Symbolic Logic 23 (4):405-441.
Finite-valued reductions of infinite-valued logics.Aguzzoli Stefano & Gerla Brunella - 2002 - Archive for Mathematical Logic 41 (4):361-399.
Modal counterparts of Medvedev logic of finite problems are not finitely axiomatizable.Valentin Shehtman - 1990 - Studia Logica 49 (3):365 - 385.
Some Ramsey theory in Boolean algebra for complexity classes.Gregory L. McColm - 1992 - Mathematical Logic Quarterly 38 (1):293-298.
A Simple Proof and Some Difficult Examples for Hindman's Theorem.Henry Towsner - 2012 - Notre Dame Journal of Formal Logic 53 (1):53-65.
Self-Embeddings of Computable Trees.Stephen Binns, Bjørn Kjos-Hanssen, Manuel Lerman, James H. Schmerl & Reed Solomon - 2008 - Notre Dame Journal of Formal Logic 49 (1):1-37.
Monotonicity and the Expressibility of NP Operators.Iain A. Stewart - 1994 - Mathematical Logic Quarterly 40 (1):132-140.
A Note on Weakly Dedekind Finite Sets.Pimpen Vejjajiva & Supakun Panasawatwong - 2014 - Notre Dame Journal of Formal Logic 55 (3):413-417.
Passages between finite and infinite.Alexander Abian - 1978 - Notre Dame Journal of Formal Logic 19 (3):452-456.
Analytics
Added to PP
2010-08-24
Downloads
32 (#712,194)
6 months
3 (#1,481,767)
2010-08-24
Downloads
32 (#712,194)
6 months
3 (#1,481,767)
Historical graph of 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.
References found in this work
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.
Countable algebra and set existence axioms.Harvey M. Friedman - 1983 - Annals of Pure and Applied Logic 25 (2):141.
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.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-667477cd97-9l5tj dc2