Cancellation laws for polynomial-time p-isolated sets

https://doi.org/10.1016/0168-0072(92)90071-7Get rights and content
Under an Elsevier user license
open archive

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 (polynomial-time equivalence types) of p-time p-isolated sets with functions induced by fully p-time combinatorial operators (which induce the original p-time computable combinatorial functions of the natural numbers).

Cited by (0)

Research partly supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University, Ithaca, NY 14850, United States, partly by the University of Florida, Gainesville, FL, United States, and partly by the Lehrstuhl für Rechnertechnik und Rechnerorganisation, Institut für Informatik, Technische Universität München.

∗∗

Research partly supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University, Ithaca, NY 14850, United States, and by NSF grant # DMS 90-06413.