✦ LIBER ✦

On P-Immunity of Exponential Time Complete Sets

✍ Scribed by Nicholas Tran

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 582 KB
Volume: 54
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1997.1488

No coin nor oath required. For personal study only.

✦ Synopsis

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*, where 7=[0, 1]. We identify 7* with Z since there is a polynomial-time computable and invertible bijection mapping one set to the other. Tally languages are subsets of [0]*. The length of article no.

📜 SIMILAR VOLUMES

On polynomial time isomorphisms of some

On polynomial time isomorphisms of some new complete sets

✍ J. Hartmanis; L. Berman 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 243 KB

On exponentiation of G-sets

✍ Andreas Blass 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 665 KB

We show that Joyal's rule of signs in combinatorics arises naturally from Dress's concept of exponentiation of virtual G-sets. We also show that two finite G-sets admit a G-equivariant bijection between their power sets if and only if the (complex) linear representations they determine are equivalen

A note on bi-immunity and p-closeness of

A note on bi-immunity and p-closeness of p-cheatable sets in P/poly

✍ Judy Goldsmith; Deborah Joseph; Paul Young 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 906 KB

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 existence of complete sets for bounde

On existence of complete sets for bounded reducibilities

✍ Valeriy Bulitko; Vadim Bulitko 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB

## Abstract Classical reducibilities have complete sets __U__ that any recursively enumerable set can be reduced to __U__. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteristics of classical complete sets are selected and a natural hi

On Some Complexity Characteristics of Im

On Some Complexity Characteristics of Immune Sets

✍ Valeriy K. Bulitko 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 363 KB 👁 1 views

## Abstract We suggest some new ways to effectivize the definitions of several classes of simple sets. On this basis, new completeness criterions for simple sets are obtained. In particular, we give descriptions of the class of complete maximal sets.