๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On polynomial time isomorphisms of some new complete sets

โœ Scribed by J. Hartmanis; L. Berman

Publisher
Elsevier Science
Year
1978
Tongue
English
Weight
243 KB
Volume
16
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Polynomial-Time Isomorphism of 1-L-Compl
Polynomial-Time Isomorphism of 1-L-Complete Sets
โœ Manindra Agrawal; Somenath Biswas ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 322 KB

Let C be any complexity class closed under log-lin reductions. We show that all sets complete for C under 1-L reductions are polynomialtime isomorphic to each other. We also generalize the result to reductions computed by finite-crossing machines. As a corollary, we show that all sets complete for C

On P-Immunity of Exponential Time Comple
On P-Immunity of Exponential Time Complete Sets
โœ Nicholas Tran ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 582 KB

We show that every many-one complete set for NEXP (co-NEXP) has an infinite subset in P. We also show that every many-one complete set for EXP has a nonsparse infinite subset in P iff annihilating functions do not exist. ] 1997 Academic Press ## 2. PRELIMINARIES All languages are subsets of 7\*, w