Apa makalah klasik dari area teori rekursi dari teori kompleksitas?

Dua makalah yang akan saya sertakan adalah:

D. Kozen, "Pengindeksan kelas subkursif" , STOC, 1978.
R. Ladner, "Tentang Struktur Pengurangan Waktu Polinomial" , JACM, 1975.

cc.complexity-theory lo.logic computability big-list structural-complexity Kaveh
sumber

ini pasti CW

Suresh Venkat

Saya setuju dengan Suresh. Sekadar menambahkan: pertanyaan ini mungkin dapat diulangi sedemikian rupa sehingga tidak perlu menjadi komunitas wiki (mis. "Apa yang harus saya baca ketika memulai dengan teori rekursi?"), Sehingga satu jawaban saja sudah cukup. Saat ini terlalu terbuka.

Shane

kita harus menggunakan ini sebagai contoh untuk FAQ

Suresh Venkat

Jawaban:

Hajek, P. Hirarki aritmatika dan kompleksitas perhitungan . Teoritis Comp. Sci. 8 (2): 227-237, 1979. Memulai studi tentang kompleksitas set indeks (di mana "kompleksitas" mereka sering terletak di suatu tempat dalam hierarki aritmatika; lihat jawaban ini untuk pertanyaan lain .)

Pada studi derajat polinomial-waktu (kata kunci = "polinomial-time degree theory", demi pencarian di masa depan) Saya akan mengatakan makalah ini menarik (beberapa dari mereka didasarkan pada teknik Ladner):

Homer, S. Derajat minimal untuk keterulangan polinomial . J. ACM 34 (2): 480-491, 1987.
Schöning, U. pasang Minimal untuk P . Teoritis Comp. Sci. 31: 41-48, 1984.
Downey, R. Nondiamond teorema untuk reducibilitas waktu polinomial . Jurnal Ilmu Komputer dan Sistem 45 (3): 385-195, 1992.
Downey, R. dan Fortnow, L. Bahasa yang sulit seragam . Teoritis Comp. Sci. 298 (2): 303-315, 2003.
Fenner, S., Homer, S., Prium, R. dan Schaefer, hierarki M. Hiper-polinomial dan lompatan polinomial . Teoritis Comp. Sci. 262: 241-256, 2001.

Mungkin pencarian referensi maju dan mundur akan menemukan beberapa makalah lagi di area yang sama (meskipun itu bukan area yang besar!).

Joshua Grochow
sumber