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

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.$A$$W$$W\leq_T^P A$$A\leq_T^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.

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:$\mathsf{NP}$

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 \subseteq A^*$$A$$G$$G$$L$

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.$\leq_T^p$