O NPI está contido em P / poli?

29

Supõe-se que pois o inverso implicaria \ mathsf {PH} = \ Sigma_2 . O teorema de Ladner estabelece que se \ mathsf {P} \ ne \ mathsf {NP} então \ mathsf {NPI}: = \ mathsf {NP} \ setminus (\ mathsf {NPC} \ cup \ mathsf {P}) \ ne \ emptyset . No entanto, a prova não parece generalizar para \ mathsf {P} / \ text {poli} assim a possibilidade \ mathsf {NPI} \ subset \ mathsf {P} / \ text {poli} ie \ mathsf {NP} \ O subconjunto \ mathsf {NPC} \ cup \ mathsf {P} / \ text {poly} parece aberto.NPP/polyPH=Σ2PNPNPI:=NP(NPCP)P/polyNPIP/polyNPNPCP/poly

Supondo que NPP/poly (ou mesmo que a hierarquia polinomial não diminua em nenhum nível), é NPIP/poly conhecido como verdadeiro ou falso? Que evidência pode ser colocada a favor e contra?

Vanessa
fonte
5
então, "o que aconteceria se todos os problemas no NP fossem NP completos ou em P \ poly"? Por um lado isso implicaria pequenos circuitos de factoring
Sasho Nikolov
11
ps: o post seria mais legível se você soletrar "it" na parte citada. Além disso, convém usar NPP/poly no lugar de NPP como sua suposição.
Kaveh
4
Um argumento de preenchimento não mostra que isso não pode acontecer a menos que NP P / poly?
quer
3
@ PeterShor: Provavelmente estou sendo densa, mas como exatamente isso funcionaria?
Vanessa
8
@ Squark: você não está sendo denso ... Eu não tinha trabalhado exatamente como isso funcionaria, e acho que indevi um pouco o resultado. Mas aqui está a minha ideia básica. Suponha que problemas completos de NP não possam ser resolvidos em tempo e conselhos subexponenciais. Pegue um problema NP-completo X e preencha-o para que o algoritmo mais rápido para ele seja quase subexponencial. Então é NPI, para que possa ser resolvido em P / poli. Isso significa que o problema NP-completo X pode ser resolvido no tempo apenas um pouco mais lento que o tempo P / poli. Por redução polinomial, agora todos os problemas completos de NP podem ser resolvidos em um pouco mais lento que o tempo P / poli.
Peter Shor

Respostas:

18

Aqui está uma alternativa possível a um argumento de preenchimento, baseado na generalização de Schöning do teorema de Ladner. Para entender o argumento, você precisa ter acesso a este documento (que infelizmente estará atrás de um muro de pagamento para muitos):

Uwe Schöning. Uma abordagem uniforme para obter conjuntos diagonais em classes de complexidade. Teórico Computer Science 18 (1): 95-103, 1982.

Vamos aplicar o teorema principal desse artigo para e serem linguagens e e como classes de complexidade, como a seguir:A1A2C1C2

  • A1= (ou qualquer idioma em )P
  • A2=SAT
  • C1=NPC
  • C2=NPP/poly

Por uma questão de clareza, o fato de provarmos que é implica .NPP/polyNPIP/poly

Supondo que tenhamos e . É claro que e estão fechados sob variações finitas. O artigo de Schöning inclui uma prova de que é recursivamente apresentável (cuja definição precisa pode ser encontrada no artigo), e a parte mais difícil do argumento é provar que é recursivamente apresentável.A umaC 1 A 2C 2 C 1 C 2 C 1 C 2NPP/polyA1C1A2C2C1C2C1C2

Sob essas suposições, o teorema implica que existe uma linguagem que não está em nem em ; e dado que , sustenta que é Karp-redutível a e, portanto, . Dado que está em mas não está nem em , segue-se que .C 1 C 2 Um 1P A A 2 A N P A N P N P N PP / p o l y N P IP / p o l yAC1C2A1PAA2ANPANPNPNPP/polyNPIP/poly

Resta provar que é recursivamente apresentável. Basicamente, isso significa que existe uma descrição explícita de uma sequência de máquinas determinísticas de Turing que todos param em todas as entradas e são tais que . Se houver um erro no meu argumento, provavelmente está aqui, e se você realmente precisar usar esse resultado, precisará fazer isso com cuidado. De qualquer forma, combinando todas as máquinas de Turing não determinísticas de tempo polinomial (que podem ser simuladas deterministicamente porque não nos importamos com o tempo de execução de cadaM 1 , M 2 , ... N PP / p o l y = { L ( H k ) : k = 1 , 2 , ... } H K H K H KNPP/polyM1,M2,NPP/poly={L(Mk):k=1,2,}Mk) e todos os polinômios, representando limites superiores no tamanho de uma família de circuitos booleanos para um determinado idioma, acredito que não é difícil obter uma enumeração que funcione. Em essência, cada pode testar se seu NTM de tempo polinomial correspondente concorda com alguma família de circuitos de tamanho polinomial até o comprimento da cadeia de entrada que é fornecida pesquisando todos os circuitos booleanos possíveis. Se houver acordo, o como o NTM, caso contrário, ele rejeita (e, como resultado, representa uma linguagem finita).MkMk

A intuição básica por trás do argumento (que está oculta no resultado de Schöning) é que você nunca pode ter duas classes de complexidade "agradáveis" (ou seja, com apresentações recursivas) sendo disjuntas e sentadas juntas. A "topologia" de classes complexas não permite: você sempre pode construir uma linguagem adequadamente entre as duas classes alternando de alguma forma as duas para trechos extremamente longos de comprimentos de entrada. O teorema de Ladner mostra isso para e , e a generalização de Schöning permite fazer o mesmo em muitas outras classes.N P CPNPC

John Watrous
fonte
7
Este é um link para as publicações de Schöning disponíveis on-line gratuitamente, incluindo a que você se refere: uni-ulm.de/in/theo/m/schoening/…
Alessandro Cosentino
11
Muito obrigado pela sua resposta! O engraçado é que eu conhecia o teorema de Shoening, mas, por alguma razão tola, pensei que não se aplica nesse caso. Btw, o texto está disponível gratuitamente, mesmo em sciencedirect
Vanessa
11
@Squark: Não é tolice suspeitar que o teorema de Schöning não se aplica, dado que P / poly inclui linguagens não recursivas. Suponho que seja uma boa sorte que possamos cruzá-lo com o NP e ainda obter o resultado.
precisa
11
@JohnWatrous: Sim, esta é precisamente a razão pela qual eu estava confuso.
Vanessa
15

Gostaria apenas de escrever uma versão de um argumento de preenchimento, conforme descrito nos comentários. Não vejo por que é necessária uma lacuna. Queremos mostrar que, se NP não está contido em P / poli, existe um problema intermediário de NP não contido em P / poli.

Existe uma função ilimitada tal que SAT não possui circuitos de tamanho menor que e, portanto, existe uma função que é ilimitada, crescente e . Deixe SAT 'denotar o idioma obtido preenchendo cadeias SAT de comprimento a . Então:n f ( n ) g g ( n ) = o ( f ( n ) ) n n g ( n )fnf(n)gg(n)=o(f(n))nng(n)

  • SAT 'está em NP (veja abaixo!)
  • SAT 'não está em P / poli: dados circuitos de tamanho para SAT', obtemos circuitos de tamanho para SAT, mas isso é menor que para alguns .n g ( n ) k n f ( n ) nnkng(n)knf(n)n
  • Não há redução de P / poli de SAT para SAT ': suponha, por contradição, que haja circuitos do tamanho para SAT, permitindo portões SAT'. Escolha suficientemente grande que e deixar . Cada porta SAT 'em possui no máximo entradas. Removendo as entradas de preenchimento, podemos cortar os portões do SAT 'em em um portão SAT com menos de entradas, que podemos simular usando - os portões do SAT resultantes têm no máximo entradas. Repetindo isso e tratando manualmente, o SAT teria circuitos de aproximadamente tamanhon k N g ( CnnkNn>NCnnkCng(N)>2kn>NCnnkCn Cn nk/2CNO(nknk/2nk/4)O(n2k)nf(n)nCnnk/2CNO(nknk/2nk/4)O(n2k) que é menor que para alguns .nf(n)n

Editar:

A escolha de é um pouco complicada. Se você está feliz em colocar SAT 'na versão promissora do NP, esse bit é desnecessário.g

Defina como o número inteiro máximo, de modo que não exista um circuito de tamanho para o comprimento strings para SAT. Defina por um algoritmo que calcula para e para após o tempo ou quando , e retorna o piso da raiz quadrada do valor mais alto encontrado neste momento . Assim, é ilimitada e e pode ser calculado em tempo . Agora observe que os argumentos acima se baseiam apenas em SAT sem circuitos de tamanho para infinitosn f ( n ) n g ( n ) f ( m ) m = 1 , 2 , n m = n g ( n ) lim inf g ( n ) / f ( n ) = 0f(n)nf(n)ng(n)f(m)m=1,2,nm=ng(n)lim infg(n)/f(n)=0g(n)nnf(n)n.

Também acho interessante ver uma prova abrindo buracos no SAT como em http://blog.computationalcomplexity.org/media/ladner.pdf . Sem o requisito de NP, isso é bastante fácil: existe uma sequência modo que nenhum tamanho do circuito detecta cadeias SAT de comprimento ; restrinja SAT a cadeias de comprimento para alguns .n1<n2<(nk)knn22ii

Colin McQuillan
fonte
11
Depois de ver a resposta de @ JohnWatrous, lembrei-me da prova de Impagliazzo do teorema de Ladner preenchendo (cf. o apêndice de Downey e Fortnow "Uniformly Hard Languages": cs.uchicago.edu/~fortnow/papers/uniform.pdf ). De fato, sua prova é basicamente a prova de Ladner por Impagliazzo, mas adaptada a essa situação. Arrumado!
Joshua Grochow
11
Muito obrigado pela sua resposta! Peço desculpas por não ter selecionado, mas tive que escolher um e o argumento de Watrous foi mais fácil de seguir, pois usava um resultado que eu já sabia. Esta é uma maneira bastante subjetiva de escolher, mas eu não poderia fazer melhor. De qualquer forma, é bom ter mais de uma maneira para se chegar a um resultado interessante
Vanessa
11
@ Squark: absolutamente - e eu também assumi que o teorema de Schöning não se aplicava.
Colin McQuillan
-13

(NPI P / poli) (P NP)

vzn
fonte
8
é conhecido e trivial: se P = NP, então . também esta não é a pergunta, a pergunta é o inverso do que você escreveu, e foi convincentemente respondida por Colin, tanto quanto posso ver. NPINP=PP/pol
Sasho Nikolov 12/12/12
a pergunta é intitulada "o NPI está contido no P / Poly" e acha que essa é uma resposta razoável, não tenho certeza se é realmente trivial devido à maneira como o NPI é geralmente definido (como dependente do P NP) ... essa resposta não conflito com a outra resposta ...
vzn 12/12/12
9
Na verdade, é ainda mais obviamente trivial: se P = NP, NPI está vazio. A pergunta é claramente declarada como "NP não contido em P / poli implica NPI não em P / poli. Portanto, sua resposta 1) afirma que um fato trivial é um problema em aberto 2) não aborda a questão
Sasho Nikolov
8
Não poderia me importar menos com pontos. Pela última vez: meu primeiro comentário, a resposta de Colin e a própria pergunta estão relacionadas ao inverso muito menos trivial e mais interessante da implicação vazia que você anotou.
Sasho Nikolov 12/12/12
11
-1: às vezes o ponto perdedor parece certo
Alessandro Cosentino