Существуют ли группы с проблемами слов в произвольных P-степенях?

14

Давно известно, что при любой степени восстановления существует конечно представленная группа, проблема слова в которой есть в этой степени. У меня вопрос: верно ли то же самое для произвольных полиномиальных степеней Тьюринга? В частности, существует ли разрешимое множество , существует ли конечно представимая группа со словом W , такая, что W P T A и A P T W ? Я также был бы готов расслабиться, конечно, представлен для рекурсивного представления.AWWTPAATPW

Я подозреваю, что ответ - да, и я слышал, как другие говорили, что они это где-то читали, но я не смог найти ссылку.

Обри да Кунья
источник
Кроме того, если кто-то может прикрепить тег теории группы или группы, я был бы признателен.
Обри да Кунья
Ты прав. Исправлена.
Обри да Кунья

Ответы:

6

Я думаю, что это не известно. (Я извиняюсь - я думаю, что я также был одним из тех, кто сказал, что я вспомнил, что когда-то читал это.) Например, я считаю, что Sapir-Birget-Rips, Annals of Math 2002 были первыми, кто продемонстрировал существование группы с -полное слово (что было бы тривиальным следствием результата, запрошенного в этом вопросе). Их следствие 1.1 гласит:NP

Существует конечно представленная группа с NP-полной проблемой слова. Кроме того, для каждого языка для некоторого конечного алфавита существует конечно определенная группа G такая , что недетерминирован временная сложность G полиномиально эквивалентна недетерминированном временной сложности L .LAAGGL

Хотя вторая половина этого следствия в некотором роде схожа с этим вопросом, он далек от доказательства того, что каждая степень содержит проблему слова.Tp

Джошуа Грохов
источник