Let L/poly and NL be the standard complexity classes, of languages recognizable in logarithmic space by Turing machines which are deterministic with polynomially-long advice and nondeterministic without advice, respectively. We recast the question whether L/poly not superset of NL in terms of deterministic and nondeterministic two-way finite automata (2DFAS and 2NFAS). We prove it equivalent to the question whether every s-state unary 2NFA has an equivalent poly(s)-state 2DFA, or whether a poly(h)-state 2DFA can check accessibility in h-vertex graphs (even under unary encoding) or check two-way liveness in h-tall, h-column graphs. This complements two recent improvements of an old theorem of Berman and Lingas. On the way, we introduce new types of reductions between regular languages (even unary ones), use them to prove the completeness of specific languages for two-way nondeterministic polynomial size, and propose a purely combinatorial conjecturethat implies L/poly not superset of NL.
Two-way automata characterizations of L/poly versus NL / C.A. Kapoutsis, G. Pighizzini. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 56:4(2015 May), pp. 662-685.
Two-way automata characterizations of L/poly versus NL
G. Pighizzini
2015
Abstract
Let L/poly and NL be the standard complexity classes, of languages recognizable in logarithmic space by Turing machines which are deterministic with polynomially-long advice and nondeterministic without advice, respectively. We recast the question whether L/poly not superset of NL in terms of deterministic and nondeterministic two-way finite automata (2DFAS and 2NFAS). We prove it equivalent to the question whether every s-state unary 2NFA has an equivalent poly(s)-state 2DFA, or whether a poly(h)-state 2DFA can check accessibility in h-vertex graphs (even under unary encoding) or check two-way liveness in h-tall, h-column graphs. This complements two recent improvements of an old theorem of Berman and Lingas. On the way, we introduce new types of reductions between regular languages (even unary ones), use them to prove the completeness of specific languages for two-way nondeterministic polynomial size, and propose a purely combinatorial conjecturethat implies L/poly not superset of NL.File | Dimensione | Formato | |
---|---|---|---|
art:10.1007/s00224-014-9560-x.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
732.24 kB
Formato
Adobe PDF
|
732.24 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
revision.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
1.11 MB
Formato
Adobe PDF
|
1.11 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.