Algoritmos e teoria da complexidade estrutural

Muitos resultados importantes na teoria da complexidade computacional e, em particular, na teoria da complexidade "estrutural", têm a propriedade interessante de que eles podem ser entendidos como fundamentalmente seguintes (como eu o vejo ...) a partir de resultados algorítmicos, fornecendo um algoritmo ou protocolo de comunicação eficiente para alguns. problema. Isso inclui o seguinte:

• IP = PSPACE segue de um algoritmo recursivo com eficiência de espaço, simulando protocolos interativos e de um protocolo interativo eficiente para avaliar fórmulas booleanas totalmente quantificadas. De fato, qualquer igualdade de classe de complexidade A = B pode ser vista como resultado de dois algoritmos eficientes (um algoritmo para problemas em A que é eficiente em relação a B e vice-versa).
• Provar a completude de NP de algum problema é apenas encontrar um algoritmo eficiente para reduzir um problema completo de NP.
• O (indiscutivelmente!) Ingrediente crucial no Teorema da Hierarquia de Tempo é uma simulação universal eficiente de máquinas de Turing.
• $\not \supset$
• O teorema do PCP é que a amplificação eficiente de hiato é possível para problemas de satisfação de restrições.
• etc etc.

Minha pergunta (que é irremediavelmente vaga!) É a seguinte: Existem resultados importantes na teoria da complexidade estrutural (distintos dos "meta-resultados", como a barreira da relativização) que não são conhecidos por terem uma interpretação natural em termos de eficiência algoritmos (ou protocolos de comunicação)?

Para muitos limites mais baixos da complexidade algébrica, não conheço uma interpretação natural em termos de algoritmos eficientes. Por exemplo:

• a técnica de derivadas parciais de Nisan e Wigderson

• a técnica de Mignon e Ressayre (classificação de Hessian) (dando o limite inferior atualmente mais conhecido em permanente versus determinante)

• o limite de grau de Strassen (e Baur-Strassen)

• a técnica de componentes conectados de Ben-Or.

Em todos os resultados acima, eles realmente parecem estar usando uma propriedade das funções envolvidas, onde essa propriedade em si parece não ter relação com a existência de qualquer algoritmo em particular (muito menos com um algoritmo eficaz).

Para resultados não algébricos, aqui estão alguns pensamentos:

• O argumento de contagem padrão para o limite inferior da classificação não parece ter uma interpretação em termos de algoritmos eficientes. Entretanto, existe uma versão contraditória desse limite inferior [1], na qual existe um algoritmo que, dada qualquer árvore de decisão que utiliza poucas comparações, constrói eficientemente uma lista que a árvore de decisão classifica incorretamente. Mas a versão contraditória, embora não seja difícil, é significativamente mais difícil que a prova de contagem. (Observe que isso é um pouco mais forte do que o que se obtém aplicando a técnica do limite inferior do adversário, por exemplo, como nessas notas , pois em [1] o adversário em si é eficiente .)$n \log n$

• Acho que mudei de idéia sobre o PARITY não em (até a prova original, muito menos a prova de Razborov-Smolensky, como apontado por @RobinKothari). Embora o Lemma de Chaveamento possa ser visto como um algoritmo aleatório ( ou determinístico ) que permite trocar duas linhas de um circuito sem uma grande explosão de tamanho, acho que isso realmente tem um sabor diferente do que muitos resultados em complexidade, e especificamente o aqueles que você cita. Por exemplo, a prova de Williams de que o se baseia crucialmente na existência de um bom algoritmo para um problema específico. Por outro lado, se alguém pudesse provar algo como o Lemma de Chaveamento de maneira não construtiva, seria igualmente bom provar PARIDADE que não em .$AC^0$$ACC \neq NEXP$$AC^0$

Devido a esses dois últimos exemplos - especialmente a classificação, onde a prova padrão não é construtiva -, parece-me que a pergunta pode não ser apenas sobre interpretações naturais em termos de algoritmos eficientes, mas também de alguma forma sobre a construtividade / eficácia das provas de vários resultados de complexidade (dependendo do que o OP tivesse em mente). Ou seja, o limite inferior da classificação padrão não é construtivo ou algorítmico, mas há uma prova algorítmica construtiva do mesmo resultado.

[1] Atallah, MJ e Kosaraju, SR. Um limite inferior baseado em adversários para classificação . Informar. Proc. Lett. 13 (2): 55-57, 1981.