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).
Original language | English |
---|---|
Pages (from-to) | 147-172 |
Number of pages | 26 |
Journal | Annals of Pure and Applied Logic |
Volume | 56 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 29 Apr 1992 |