Recentemente, Ryan Willams provou que a Construtividade na Prova Natural é inevitável para derivar uma separação de classes de complexidade: e .
A construtividade na prova natural é uma condição que todas as provas combinatórias na complexidade do circuito satisfazem e que podemos decidir se a função de destino em (ou outras classes de complexidade "rígidas") possui uma propriedade "rígida" por um algoritmo que executa em poli-tempo no comprimento da tabela de verdade da função de destino.
As outras duas condições são: a condição inútil que requer propriedade "hard" não pode ser calculada por nenhum circuito em e a condição de grandeza que a propriedade hard é fácil de encontrar.
Minha pergunta é :
Esse resultado torna a Teoria da Complexidade Geométrica (GCT) indisponível para resolver os principais problemas de separação, como vs , vs ou vs ?N P P N C N E X P T C 0
Referências:
- Ryan Williams, " Provas naturais versus desa des randomização "
Mais alguns comentários sobre isso: a relação entre o GCT e as provas naturais foi discutida no passado (mesmo nos próprios documentos originais do GCT). Embora não pareça ter havido consenso sobre qual "construtividade" ou "grandeza" seria violada pela abordagem do TCG, Mulmuley e Sohoni argumentaram em um ponto que se o TCG pudesse ser realizado, deveria violar a grandeza. Para uma referência relevante, consulte a Seção 6 da visão geral do Regan sobre o GCT . No entanto, devo acrescentar que essa visão geral já tem 10 anos e uma quantidade considerável de trabalho foi dedicada ao GCT desde então; Não tenho a certeza se existe alguma opinião revista / nova sobre este assunto. (Talvez Josh Grochow possa gritar?)
fonte
A resposta curta é não .
A abordagem da Teoria da complexidade geométrica tem como alvo certas propriedades extremamente raras, que Mulmuley argumenta que não é "grande", conforme definido por Razborov e Rudich. Para um argumento formal, veja também a tese de Joshua Grochow , Seção 3.4.3 . A caracterização de simetria evita a barreira Razborov – Rudich e sua resposta .
O parágrafo a seguir vem de On P vs. NP e Geometric Complexity Theory, de Ketan Mulmuley ( JACM 2011 ou manuscrito ), Seção 4.3 Um Plano de Alto Nível :
Como as condições de construtividade e de grandeza são necessárias para uma prova natural (onde a utilidade é implícita), provar que a construtividade é inevitável não é suficiente para descartar tais abordagens (embora seja um grande passo adiante).
fonte