Gibt es Gruppen mit Wortproblemen in beliebigen P-Graden?

14

Es ist seit langem bekannt, dass es bei jedem Wiederholungsgrad eine endlich präsentierte Gruppe gibt, deren Wortproblem in diesem Grad liegt. Meine Frage ist, ob das Gleiche für beliebige Polynomzeit- Turing-Grade gilt. Speziell existiert bei einer entscheidbaren Menge eine endlich dargestellte Gruppe mit dem Wortproblem W , so dass W P T A und A P T W ? Ich wäre auch bereit, endlich präsentierte bis rekursiv präsentierte zu entspannen.AWWTPAATPW

Ich vermute, dass die Antwort ja lautet, und ich habe andere sagen hören, dass sie das irgendwo gelesen haben, aber ich habe es nicht geschafft, eine Referenz aufzuspüren.

Aubrey da Cunha
quelle
Auch wenn jemand eine Gruppentheorie oder ein gruppenbezogenes Tag darauf kleben könnte, würde ich es begrüßen.
Aubrey da Cunha
Du hast Recht. Fest.
Aubrey da Cunha

Antworten:

6

NP

LEINEINGGL

Tp

Joshua Grochow
quelle