Regular gegen TC0

14

RegNC1RegR e gT C 0 N C 1T C 0TC0RegRegTC0NC1TC0 nicht kennen, kennen wir auch .RegTC0

Gibt es einen Kandidaten für ein Problem in Reg , das sich nicht in ?TC0

Gibt es ein bedingtes Ergebnis, das impliziert, dass , z. B. wenn dann ? N C 1T C 0 R e gT C 0RegTC0NC1TC0RegTC0

Kaveh
quelle

Antworten:

15

Nehmen als Alphabet und Barrington erwies sich in [2] , dass ist -komplett für -Reduktion (und sogar tatsächlich mit einer restriktiveren Reduktion).S5

L={σ1σnS5σ1σn=Id}
LNC1AC0

Dies zeigt insbesondere, dass reguläre Sprachen nicht in wenn . Durch Anwendung der Halbgruppentheorie (siehe das Buch von Straubing [1] für weitere Einzelheiten) erhalten wir, dass, wenn ausschließlich in ist, alle regulären Sprachen entweder -complete oderTC0TC0NC1ACC0NC1NC1ACC0 .

[1] Straubing, Howard (1994). "Endliche Automaten, formale Logik und Schaltungskomplexität". Fortschritte in der theoretischen Informatik. Basel: Birkhäuser. p. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). Verzweigungsprogramme mit begrenzter Breite und Polynomgröße erkennen genau diese Sprachen in NC1

CP
quelle
1
Außerdem, wenn ACC 0 ist nicht „streng in NC 1 dann alle regulären Sprachen sind“ in ACC 0 sowieso.010
14

Reguläre Sprachen mit unlösbaren syntaktischen Monoiden sind -vollständig (aufgrund von Barrington; dies ist der Grund für das häufiger zitierte Ergebnis, dass N C 1 gleich einheitlichen Verzweigungsprogrammen der Breite 5 ist). Somit ist eine solche Sprache nicht in T C 0, es sei denn, T C 0 = N C 1 .NC1NC1TC0TC0=NC1

Mein bevorzugter -kompletter regulärer Ausdruck ist ( ( a | b ) 3 ( a b a | b ) ) (dies ist tatsächlich eine Codierung von S 5 , wie in der Antwort von CP).NC1((a|b)3(aba|b))S5

Emil Jeřábek unterstützt Monica
quelle
1
Was ist ein syntaktisches Monoid?
T ....
3
Warnung vor verwirrender Terminologie: In diesem Zusammenhang wird ein Monoid als unlösbar bezeichnet, wenn es eine unlösbare Gruppe als Untergruppe enthält , nicht unbedingt als Submonoid.
Emil Jeřábek unterstützt Monica am
2
Mein bevorzugter NC ^ 1-vollständiger regulärer Ausdruck ist (dies ist tatsächlich eine Kodierung von S_5, wie in der Antwort von CP). ((a|b)3(aba|b))
Emil Jeřábek unterstützt Monica am
4
Ein weiteres Beispiel, weniger präzise , aber leichter zu verstehen: das 'a' wirkt als den Zyklus (1 2 3 4 5), die " b "fungiert als Permutation (1 2), und es ist bekannt, dass diese beiden Gruppenelemente S - 5 erzeugen .
((a+b)(abababa+b))
S5
CP
3
@MichaelCadilhac: fungiert als ( 1 , 2 , 3 , 4 , 5 ) und b als ( 1 , 2 , 3 , 4 ) . Diese erzeugen S 5 als b a - 1 eine Transposition ist. a(1,2,3,4,5)b(1,2,3,4)S5ba1
Emil Jeřábek unterstützt Monica am