Давно известно, что при любой степени восстановления существует конечно представленная группа, проблема слова в которой есть в этой степени. У меня вопрос: верно ли то же самое для произвольных полиномиальных степеней Тьюринга? В частности, существует ли разрешимое множество , существует ли конечно представимая группа со словом W , такая, что W ≤ P T A и A ≤ P T W ? Я также был бы готов расслабиться, конечно, представлен для рекурсивного представления.
Я подозреваю, что ответ - да, и я слышал, как другие говорили, что они это где-то читали, но я не смог найти ссылку.
cc.complexity-theory
computability
gr.group-theory
Обри да Кунья
источник
источник
Ответы:
Я думаю, что это не известно. (Я извиняюсь - я думаю, что я также был одним из тех, кто сказал, что я вспомнил, что когда-то читал это.) Например, я считаю, что Sapir-Birget-Rips, Annals of Math 2002 были первыми, кто продемонстрировал существование группы с -полное слово (что было бы тривиальным следствием результата, запрошенного в этом вопросе). Их следствие 1.1 гласит:NP
Хотя вторая половина этого следствия в некотором роде схожа с этим вопросом, он далек от доказательства того, что каждая степень содержит проблему слова.≤pT
источник