Apakah ada kelompok dengan masalah kata dalam derajat-P yang sewenang-wenang?

Sudah lama diketahui bahwa, mengingat gelar Turing apa pun, ada grup yang dipresentasikan secara halus yang masalah kata-katanya ada di tingkat itu. Pertanyaan saya adalah apakah hal yang sama berlaku untuk waktu polinomial Turing derajat sewenang-wenang . Secara khusus, diberikan himpunan decidable, , apakah ada kelompok yang disajikan secara halus, dengan masalah kata, W , sehingga W ≤ P T A dan A ≤ P T W ? Saya juga akan bersedia untuk bersantai disajikan secara halus untuk disajikan secara rekursif.$A$$W$$W\leq_T^P A$$A\leq_T^P W$

Saya curiga jawabannya adalah ya, dan saya telah mendengar orang lain mengatakan mereka membaca ini di suatu tempat, tetapi saya belum dapat mengejar referensi.

Saya pikir ini tidak diketahui. (Saya minta maaf - saya pikir saya juga salah satu dari orang-orang yang mengatakan saya ingat pernah membaca ini di suatu tempat.) Sebagai contoh, saya percaya bahwa Sapir-Birget-Rips, Annals of Math 2002 adalah orang pertama yang menunjukkan keberadaan kelompok dengan -Lengkap kata masalah (yang akan menjadi konsekuensi sepele dari hasil yang diminta dalam pertanyaan ini). Status wajar mereka 1,1:$\mathsf{NP}$

Ada grup yang disajikan dengan masalah NP-complete word. Selain itu, untuk setiap bahasa untuk beberapa terbatas abjad A terdapat kelompok finitely disajikan G sehingga kompleksitas waktu nondeterministic dari G adalah polynomially setara dengan kompleksitas waktu nondeterministic dari L .$L \subseteq A^*$$A$$G$$G$$L$

Sementara bagian kedua dari akibat wajar ini agak mirip dengan pertanyaan ini, jauh dari membuktikan bahwa setiap -degree mengandung kata problem.$\leq_T^p$