Sabe-se que se , a hierarquia polinomial colapso para e .
Quais são os colapsos mais fortes que se sabe se o ?
circuit-complexity
complexity
Springberg
fonte
fonte
Respostas:
Creio que a mais forte é queNEXP=MA . Isso foi provado por Impagliazzo Kabanets e Wigderson.
Consulte https://scholar.google.com/scholar?cluster=17275091615053693892&hl=pt_BR&as_sdt=0,5&sciodt=0,5
Eu também estaria interessado em saber de colapsos mais fortes do que isso.
Editar (24/8): OK, pensei em algum colapso potencialmente mais forte, que se segue essencialmente das provas do artigo acima. Porque implica N E X P = E X P (ver a ligação acima), e E X P é fechada sob complemento, que também tem N E X P fechada sob complemento e, por conseguinte, N E X P = M A ∩ c o M ANEXP⊂P/poly NEXP=EXP EXP NEXP NEXP=MA∩coMA , que é um pouco mais forte. De fato, a hipótese implica que, para qualquer linguagem , uma única cadeia de testemunhas w n pode ser usada no protocolo MA correspondente para todas as instâncias YES de qualquer comprimento n , assim também N E X P = O M A ∩ c O O M A (onde S H Um = "Ignorando MA", ver Fortnow-Santhanam-me http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.156.3018&rep=rep1&type=pdfNEXP wn n NEXP=OMA∩coOMA OMA ) Essas propriedades extras, embora técnicas, podem ser úteis em algum argumento de limite inferior do circuito.
Edição 2: Parece que Andrew Morgan já destacou isso. Opa :)
fonte
Muitas coisas divertidas acontecem. A maioria dos que conheço começa com o artigo da IKW . Lá, o colapsoNEXP=MA é mostrado e (eu acho) é o colapso literal mais forte das classes de complexidade que conhecemos. Existem outros tipos de "colapsos", que eu acho que deveriam ser apontados.
O mais importante, penso eu, é a propriedade "testemunha sucinta universal" (também do artigo da IKW). Por um lado, fornece uma ferramenta a partir da qual muitos dos outros colapsos são conseqüências diretas; por outro, os limites inferiores do circuito recente (por exemplo, aqui e aqui ) para oNEXP exploram essa conexão. Resumidamente, a propriedade diz que, para cada NEXP linguagem L , e qualquer NEXP -máquinasferramentas M decidir L , cada x∈L tem uma forma sucinta descritível testemunha de acordo com M . Formalmente, existe um polinômio p dependendo daM modo que para cadax∈L , existe um circuitoCx de tamanhop(|x|) modo que a tabela verdade deCx seja uma sequência de opções não determinísticas paraM que levam à aceitação na entradax .
A sucessão das testemunhas é útil, porque você pode rederir diretamente muitos dos outros colapsos dela. Por exemplo, segue-se trivialmente queNEXP=coNEXP=EXP . Por exemplo, suponha que L é em NEXP através de um NEXP -máquinasferramentas M . A propriedade de testemunha sucinta diz que há um polinômio p para que M tenha testemunhas sucintas do tamanho p . Podemos então decidir L em EXP , na entrada x , forçando com força bruta todos os circuitos de tamanho no máximo p(|x|) e verificando se eles codificam uma sequência de opções que levam aM aceitar na entradax . Você pode combinar isso com o resultado (anteriormente conhecido por provas interativas) queEXP⊆P/poly⟹EXP=MA para concluirNEXP⊆P/poly⟹NEXP=MA .
Vale ressaltar que podemos escolherM e, portanto, a forma das testemunhas. Por exemplo, você pode realmente concluir a partir de " NEXP tem testemunhas sucintas universais" que NEXP=OMA=co-OMA . Aqui o OMA é "inconsciente-MA", significando que existe um Merlin honesto que depende apenas do comprimento da entrada. É fácil ver que OMA⊆P/poly , basicamente, isso apenas fornece uma forma normal de como as linguagens NEXP são computadas em P/poly sob a suposição de que NEXP⊆P/poly em primeiro lugar. Aqui está uma maneira de ver o colapso do OMA :
[Graças a Cody Murray por apontar o truque de utilizar a entrada para contar o número de cordas emL . Anteriormente eu tinha M′ uso que se NEXP⊆P/poly , em seguida, NEXP=EXP para anotar a tabela de verdade do L , mas a estratégia de Cody é mais elegante.]
Como nota final, embora tecnicamente implícito emNEXP=MA , o colapso NEXP=PSPACE tem outra implicação interessante. É sabido que o PSPACE possui uma linguagem completa, que é auto-redutível em baixa e auto-redutível aleatória. Normalmente, todos esses idiomas estão dentro do PSPACE e, portanto, não devemos esperar dizer (incondicionalmente) que o NEXP tem um idioma tão completo, desde que esperemos que o NEXP≠PSPACE . No entanto, se NEXP=PSPACE , NEXP nãotem esses idiomas completos. Uma afirmação semelhante (substituindo NEXP por EXP ) foi usada por Impagliazzo e Wigderson para concluir uma espécie de "dicotomia de des randomização" para BPP em relação a EXP , portanto, pode ser útil para descobrir outras consequências de NEXP⊆P/poly .
fonte