Cancellation laws for polynomial-time p-isolated sets

&
Annals of Pure and Applied Logic 56 (1-3):147-172 (1992)
  Copy   BIBTEX

Abstract

A universal Horn sentence in the language of polynomial-time computable combinatorial functions of natural numbers is true for the natural numbers if, and only if, it is true for PETs of p-time p-isolated sets with functions induced by fully p-time combinatorial operators

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(92)90071-7

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,745

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

Every polynomial-time 1-degree collapses if and only if P = PSPACE.Stephen A. Fenner, Stuart A. Kurtz & James S. Royer - 2004 - Journal of Symbolic Logic 69 (3):713-741.
BLASS. A., A game semantics for linear logic CENZER, D. and REMMEL, J., Polynomial-time Abehan groups CLOTE, P. and TAKEUTI, G., Bounded arithmetic for NC, ALogTIME, L and NL. [REVIEW]P. Lincoln, J. Mitchell & A. Scedrov - 1992 - Annals of Pure and Applied Logic 56:365.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
A second-order system for polytime reasoning based on Grädel's theorem.Stephen Cook & Antonina Kolokolova - 2003 - Annals of Pure and Applied Logic 124 (1-3):193-231.
Feasible graphs with standard universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 94 (1-3):21-35.
On the lattices of NP-subspaces of a polynomial time vector space over a finite field.Anil Nerode & J. B. Remmel - 1996 - Annals of Pure and Applied Logic 81 (1-3):125-170.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
On the computability of fractal dimensions and Hausdorff measure.Ker-I. Ko - 1998 - Annals of Pure and Applied Logic 93 (1-3):195-216.
Higher type recursion, ramification and polynomial time.Stephen J. Bellantoni, Karl-Heinz Niggl & Helmut Schwichtenberg - 2000 - Annals of Pure and Applied Logic 104 (1-3):17-30.
The algebraic structure of the isomorphic types of tally, polynomial time computable sets.Yongge Wang - 2002 - Archive for Mathematical Logic 41 (3):215-244.

Analytics

Added to PP
2014-01-16

Downloads
9 (#449,242)

6 months
3 (#1,723,834)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Combinatorial Functors.J. N. Crossley & Anil Nerode - 1977 - Journal of Symbolic Logic 42 (4):586-587.
Recursive Equivalence Types and Combinatorial Functions.John Myhill - 1966 - Journal of Symbolic Logic 31 (3):510-511.
Extensions to Isols.Anil Nerode - 1960 - Journal of Symbolic Logic 25 (4):359-361.

Add more references