Quais são os trabalhos clássicos da área teórica da recursão da teoria da complexidade?

14

Dois artigos que eu incluiria são:

  1. D. Kozen, "Indexação de classes sub-recursivas" , STOC, 1978.

  2. R. Ladner, "Sobre a estrutura da redutibilidade do tempo polinomial" , JACM, 1975.

Kaveh
fonte
1
esse deve ser o CW
Suresh Venkat
1
Eu concordo com Suresh. Apenas para acrescentar: essa pergunta provavelmente poderia ser reformulada de tal forma que não precisaria ser um wiki da comunidade (por exemplo, "O que devo ler ao iniciar a teoria da recursão?"), De modo que uma única resposta seja suficiente. Atualmente, é muito aberto.
Shane
devemos usar isso como um exemplo para o FAQ
Suresh Venkat

Respostas:

11

Hajek, P. Hierarquia aritmética e complexidade da computação . Theoret. Comp. Sci. 8 (2): 227-237, 1979. Iniciou o estudo das complexidades dos conjuntos de índices (onde suas "complexidades" geralmente se encontram em algum lugar da hierarquia aritmética; veja esta resposta para outra pergunta ).

No estudo dos graus de tempo polinomial (palavra-chave = "teoria dos graus de tempo polinomial", para fins de pesquisas futuras), eu diria que esses trabalhos são de interesse (vários deles são baseados na técnica de Ladner):

Provavelmente, uma pesquisa de referência para frente e para trás encontrará vários outros artigos na mesma área (embora não seja uma área tão grande!).

Joshua Grochow
fonte