Czy istnieją grupy z problemami słownymi w dowolnych stopniach P?

14

Od dawna wiadomo, że przy dowolnym stopniu reuringu istnieje dobrze przedstawiona grupa, której problem słowny jest w tym stopniu. Moje pytanie brzmi, czy to samo dotyczy dowolnych stopni Turinga w czasie wielomianowym . W szczególności, biorąc pod uwagę rozstrzygalny zestaw, , czy istnieje precyzyjnie przedstawiona grupa z problemem słownym , taka, że i ? Byłbym także skłonny odpocząć od prezentacji skończonej do prezentacji rekurencyjnej.ZAW.W.T.P.ZAZAT.P.W.

Podejrzewam, że odpowiedź brzmi „tak” i słyszałem, jak inni mówią, że gdzieś to czytają, ale nie byłem w stanie zgonić referencji.

Aubrey da Cunha
źródło
Byłbym też wdzięczny, gdyby ktoś mógł nakleić na to teorię grupy lub tag związany z grupą.
Aubrey da Cunha,
Masz rację. Naprawiony.
Aubrey da Cunha,

Odpowiedzi:

6

Myślę, że to nie jest znane. (Przepraszam - myślę, że byłem także jedną z osób, które powiedziały, że pamiętałem gdzieś to czytać.) Na przykład uważam, że Sapir-Birget-Rips, Annals of Math 2002 jako pierwsze pokazały istnienie grupy z problem z pełnymi słowami (co byłoby banalną konsekwencją wyniku zadanego w tym pytaniu). Ich następstwo 1.1 stanowi:N.P.

Istnieje skończona grupa przedstawiająca problem z słowem kompletnym NP. Ponadto, dla każdego języka dla niektórych skończonych alfabet istnieje skończona przedstawiony grupy , że czas niedeterministyczny złożoność jest wielomianowo równoważny czas niedeterministycznych złożoności .L.ZAZAsolsolL.

Podczas gdy druga połowa tego wniosku jest w pewnym podobna do tego pytania, jest to dalekie od udowodnienia, że ​​każdy stopień zawiera problem słowny.T.p

Joshua Grochow
źródło