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

Polynomial-Time Isomorphism of 1-L-Complete Sets

โœ Scribed by Manindra Agrawal; Somenath Biswas

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
322 KB
Volume
53
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 under two-way DFA reductions are polynomial-time isomorphic to each other.

๐Ÿ“œ SIMILAR VOLUMES

Almost all trees share a complete set of
Almost all trees share a complete set of immanantal polynomials
โœ Phillip Botti; Russell Merris ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 371 KB

## Abstract Let ฯ‡ be an irreducible character of the symmetric group __S__~__n__~. For an __n__โ€byโ€__n__ matrix __A__ = (__a__~__ij__~), define equation image If __G__ is a graph, let __D__(__G__) be the diagonal matrix of its vertex degrees and __A__(__G__) its adjacency matrix. Let __y__ and __