Desmorona sob a suposição de que

13

Sabe-se que se , a hierarquia polinomial colapso para e .NPP/PolyΣ2PMA=AM

Quais são os colapsos mais fortes que se sabe se o ?NEXPP/Poly

Springberg
fonte
É, de facto, "conhecido que se então a hierarquia polinomial colapsa para" O P . 2NPP/poly2

Respostas:

14

Creio que a mais forte é que NEXP=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 ANEXPP/polyNEXP=EXPEXPNEXPNEXP=MAcoMA, 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=pdfNEXPwnnNEXP=OMAcoOMAOMA) 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 :)

Ryan Williams
fonte
15

Muitas coisas divertidas acontecem. A maioria dos que conheço começa com o artigo da IKW . Lá, o colapso NEXP=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 o NEXP exploram essa conexão. Resumidamente, a propriedade diz que, para cada NEXP linguagem L , e qualquer NEXP -máquinasferramentas M decidir L , cada xL tem uma forma sucinta descritível testemunha de acordo com M . Formalmente, existe um polinômio p dependendo daM modo que para cadaxL , 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 que NEXP=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) queEXPP/polyEXP=MA para concluirNEXPP/polyNEXP=MA .

Vale ressaltar que podemos escolher M 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 OMAP/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 NEXPP/polyem primeiro lugar. Aqui está uma maneira de ver o colapso do OMA :

Para um idioma LNEXP decidido por uma máquina M , construa uma máquina NEXPM seguinte maneira. Veja a entrada de n bits como um número N entre 1 e 2n . Para cada x de comprimento n , suponha uma testemunha wx e execute M(x,wx) para verificá-la. M(N)aceita se e somente se M aceita pelo menos N valores de x . As suposições estão dispostas de tal forma que uma descrição sucinta de uma testemunha para M é um circuito C que calcula o mapa (x,i) o i -ésimo bit de wx . Agora, suponha que N seja exatamente o número de cadeias de caracteres em L no comprimento n . Em seguida, testemunhas sucinto para M na entrada N são circuitos que codificam simultaneamente todos deM testemunhas 's para Length-n entradas. Em particular, seM tem testemunhas sucintas, todas as testemunhas deM ' podem ser descritas simultaneamente pelo mesmo circuito.

Para concluir a reivindicação, lembramos que NEXP=PCP[poly,poly] . Permitindo que M seja a máquina que adivinha o PCP e, em seguida, simula deterministicamente o verificador, o parágrafo acima nos diz a existência de PCPs simultaneamente descritos de forma sucinta para todos os idiomas do NEXP . Portanto, agora para obter NEXP=OMA , Merlin envia a descrição sucinta dos PCPs para todas as entradas com o comprimento atual, que Arthur pode verificar apenas conectando sua entrada e executando o verificador PCP.

[Graças a Cody Murray por apontar o truque de utilizar a entrada para contar o número de cordas em L . Anteriormente eu tinha M uso que se NEXPP/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 em NEXP=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 NEXPPSPACE . 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 NEXPP/poly .

Andrew Morgan
fonte
BTW, não confie que o cidadão tenha as versões mais recentes (ou mesmo as melhores) dos meus trabalhos. Aqui está melhor :) web.stanford.edu/~rrwill/projects.html
Ryan Williams
Obrigado pelo conselho! Vou ter isso em mente para o futuro (e que provavelmente também se aplica a outros autores).
Andrew Morgan