Zwykły kontra TC0

14

Według Zoo Złożoności , RegNC1 i wiemy, że Reg nie może się liczyć, więc TC0Reg . Jednakże nie mówi, czy RegTC0 czy nie. Ponieważ nie znamy NC1TC0 , nie znamy również RegTC0 .

Czy jest kandydatem do problemu w , który nie jest w T C 0 ?RegTC0

Czy istnieje wynik warunkowy sugerujący, że , np. Jeśli N C 1T C 0, to R e gT C 0 ?RegTC0NC1TC0RegTC0

Kaveh
źródło

Odpowiedzi:

15

Weź jako alfabet i L = { σ 1σ nS 5σ 1σ n = Id } Barrington udowodnił w [2], że L jest NC 1 -kompletne dla redukcji AC 0 (a nawet z bardziej restrykcyjna redukcja).S5

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

W szczególności pokazuje to, że zwykłe języki nie są w jeśli TC 0NC 1 . Stosując teorię półgrup (więcej szczegółów znajduje się w książce Straubinga [1]), otrzymujemy, że jeśli ACC 0 jest ściśle w NC 1, wówczas wszystkie zwykłe języki są albo kompletne NC 1, albo ACC 0 .TC0TC0NC1ACC0NC1NC1ACC0

[1] Straubing, Howard (1994). „Automaty skończone, logika formalna i złożoność obwodów”. Postęp w informatyce teoretycznej. Bazylea: Birkhäuser. p. 8. ISBN 3-7643-3719-2.

[2] Barrington, David A. Mix (1989). „Wielomianowe programy rozgałęziające o ograniczonej szerokości rozpoznają dokładnie te języki w NC1”

CP
źródło
1
Ponadto, jeśli ACC 0 nie jest „ściśle w NC 1, wówczas wszystkie zwykłe języki są” w ACC 0 .010
14

Zwykły języki z nierozwiązywalne składniowych monoids są -Complete (ze względu na Barrington, co jest powodem za bardziej powszechnie cytowane wyniku czego N C 1 równa jednakowe szerokości 5 programów rozgałęzienia). Tak więc, każdy taki język nie jest T C 0 ile nie T C 0 = N C 1 .NC1NC1TC0TC0=NC1

Moim ulubionym wyrażeniem regularnym zawierającym jest ( ( a | b ) 3 ( a b a | b ) ) (w rzeczywistości jest to kodowanie S 5 , jak w odpowiedzi CP).NC1((a|b)3(aba|b))S5

Emil Jeřábek 3.0
źródło
1
co to jest monoid składniowy?
T ....
3
Ostrzeżenie przed mylącą terminologią: w tym kontekście mówi się, że monoid jest nierozwiązywalny, jeśli zawiera nierozwiązywalną grupę jako podgrupę , niekoniecznie jako submonoid.
Emil Jeřábek 3.0
2
Moje ulubione wyrażenie regularne z NC ^ 1 to (w rzeczywistości jest to kodowanie S_5, jak w odpowiedzi CP). ((a|b)3(aba|b))
Emil Jeřábek 3.0
4
((a+b)(abababa+b))
S5
3
a(1,2,3,4,5)b(1,2,3,4)S5ba1