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.
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.
cc.complexity-theory
computability
gr.group-theory
Aubrey da Cunha
źródło
źródło
Odpowiedzi:
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.
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.≤pT.
źródło