✦ LIBER ✦

Isomorphisms and 1-L reductions

✍ Scribed by Eric W. Allender

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 854 KB
Volume: 36
Category: Article
ISSN: 0022-0000
DOI: 10.1016/0022-0000(88)90033-5

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Reductions to Graph Isomorphism

✍ Jacobo Torán 📂 Article 📅 2008 🏛 Springer 🌐 English ⚖ 382 KB

Design isomorphisms and group isomorphis

Design isomorphisms and group isomorphisms

✍ Neal Brand 📂 Article 📅 1988 🏛 Springer 🌐 English ⚖ 559 KB

Order Isomorphisms and Lattice-Homomorph

Order Isomorphisms and Lattice-Homomorphism Projections in l∞

✍ B. Nassopoulos; P.C. Tsekrekos 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 415 KB

Steiner systems andn−1-isomorphisms

✍ Gaetano Quattrocchi; Gloria Rinaldi 📂 Article 📅 1997 🏛 Springer 🌐 English ⚖ 810 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

Isomorphisms and non-isomorphisms of at

Isomorphisms and non-isomorphisms of at actions

✍ David Handelman 📂 Article 📅 2009 🏛 Springer-Verlag 🌐 English ⚖ 803 KB