Was sind die klassischen Arbeiten aus dem rekursionstheoretischen Bereich der Komplexitätstheorie?

14

Zwei Papiere, die ich einschließen würde, sind:

  1. D. Kozen, "Indexing of subrecursive classes" , STOC, 1978.

  2. R. Ladner, "Über die Struktur der Polynomzeitreduzierbarkeit " , JACM, 1975.

cc.complexity-theory lo.logic computability big-list structural-complexity Kaveh
quelle
1
Dies sollte CW sein
Suresh Venkat
1
Ich stimme Suresh zu. Nur um hinzuzufügen: Diese Frage könnte wahrscheinlich so umformuliert werden, dass es sich nicht um ein Community-Wiki handeln müsste (z. B. "Was soll ich lesen, wenn ich mit der Rekursionstheorie beginne?"), Sodass eine einzige Antwort ausreichen könnte. Es ist derzeit zu offen.
Shane
Wir sollten dies als Beispiel für die FAQ verwenden
Suresh Venkat

Antworten:

11

Hajek, P. Arithmetische Hierarchie und Komplexität der Berechnung . Theoret. Comp. Sci. 8 (2): 227-237, 1979. Beginn der Untersuchung der Komplexität von Indexmengen (wobei ihre "Komplexität" häufig irgendwo in der arithmetischen Hierarchie liegt; siehe diese Antwort auf eine andere Frage ).

Zum Studium von Polynom-Zeit-Graden (Schlagwort = "Polynom-Zeit-Grad-Theorie", für zukünftige Recherchen) würde ich sagen, dass diese Artikel von Interesse sind (einige davon basieren auf Ladners Technik):

Wahrscheinlich werden bei einer Referenzsuche in Vorwärts- und Rückwärtsrichtung mehrere Artikel in demselben Bereich gefunden (obwohl es sich nicht um einen so großen Bereich handelt!).

Joshua Grochow
quelle