Dureza de funções booleanas ruidosas

13

Seja uma função booleana de variáveis ​​booleanas. Seja o valor esperado de quando é obtido a partir de ao inverter cada coordenada com probabilidade .fg ( x ) = T ϵ ( f ) ( x ) f ( y ) y x ϵ / 2ng(x)=Tϵ(f)(x)f(y)yxϵ/2

Estou interessado em casos em que é computacionalmente difícil aproximar . Deixe-me fixar uma noção de "aproximação" (mas pode haver outras): Uma função booleana aproxima se quando e quando .Um argumento de contagem (baseado na existência de códigos de correção de erro de taxa positiva) parece dar a existência de funções booleanas para as quais essa aproximação requer um circuito de tamanho exponencial. Mas a questão é o que acontece quando é no NP ou na vizinhança.h g h ( x ) = 1 g ( x ) 0,9 h ( x ) = 0 g ( x ) 0,1 fghgh(x)=1g(x)0.9h(x)=0g(x)0.1f

Q1: Existe um exemplo de descrito pelo circuito NP (ou espaço P) para que cada seja NP rígido ou rígido, em algum sentido mais fraco.hfh

Para ver que nem sempre é fácil (agradeço a Johan Hastad pela discussão útil sobre isso), podemos considerar a propriedade dos gráficos de ter um clique de tamanho , para entrada aleatória, é concebível que É difícil detectar se existe um clique grande, mas isso se manifesta por ter mais do que o esperado cliques de tamanho log n no gráfico barulhento. Nesse caso, qualquer será provavelmente difícil (mas não comprovadamente, e não terrivelmente difícil, como dirão os circuitos quase polinomiais).N 1 / 4 hhn1/4h

P2: Qual é a situação se começar com baixa complexidade? ( , monótono , etc.)A C 0 T C 0 A C CfAC0TC0ACC

T3: Qual é a situação para alguns exemplos básicos de funções booleanas? (A questão pode ser estendida também à função com valor real.)

Q4: A pergunta acima pode ser formalizada para o modelo uniforme de computação (máquina de Turing)?

Atualização: Em vista da resposta de Andy (Olá, Andy), acho que a pergunta mais interessante é entender a situação para várias funções específicas.

Atualizar Outra pergunta Q5 [Q1 para funções monótonas] (também em vista da resposta de Andy). Qual é a situação se é monótono? Ainda podemos codificar de forma robusta uma pergunta completa do NP>f

Gil Kalai
fonte
imho esta questão na aproximação do circuito está relacionada. sua pergunta parece ser semelhante à pergunta P / poli vs NP.
vzn

Respostas:

14

para a pergunta 1, a resposta é sim e pode ser mostrada da seguinte maneira. (Também esboçarei implicitamente uma resposta afirmativa para o quarto trimestre, já que o argumento é uniforme e tratará todos os comprimentos de entrada de uma só vez.)

Corrija qualquer linguagem NP completa e uma família de bons códigos binários de correção de erros (com taxa de 1/4 e correção de uma fração de 0,1 dos erros, digamos). Seja E n c n : { 0 , 1 } n{ 0 , 1 } 4 n seja a função de codificação para o comprimento n ; usamos algum código em que E n c = { E n c n } é computável por um algoritmo de tempo polinomial uniforme.LEncn:{0,1}n{0,1}4nnEnc={Encn}

Defina como o conjunto de cadeias z que estão dentro da distância, no máximo, 0,05 | z | a partir de uma palavra de código Y E n c ( L ) que codifica um elemento de L . Note-se que L ' está em NP, como você pode imaginar e verificar a palavra de código nas proximidades, a palavra decodificada, eo certificado NP para a adesão da palavra decodificada em L . Lz.05|z|yEnc(L)LLL

Então a alegação é que qualquer "aproximação" de no seu sentido é NP-difícil para ε = 0,01 . Para se considerarmos uma palavra-código válido y = E n c ( x ) de algum comprimento 4 n , em seguida, com probabilidade 1 - o ( 1 ) ao longo de um aleatória ε -perturbed versão y ' de y , vai discordar y em, no máximo, uma fração 0,05 de coordenadas e, portanto, discorda de qualquer outra palavra de código de E n cLε=.01y=Enc(x)4n1o(1)εyyy em umafração demais do que 0,05 das cordas. Para tal y ' temos y 'L ' sse x L . Portanto, se h é uma aproximação àversão ε suavizada de L no seu sentido, então devemos ter h ( y ) = L ( x ) . Como E n c é eficientemente computável, isso nos permite reduzir de maneira eficiente as questões de associação de L para as de h . entãoEncn.05yyLxLhεLh(y)=L(x)EncLh é NP-difícil.h

Duas notas:

(1) codificações de correção de erros de instâncias NP foram usadas anteriormente em vários artigos, especialmente
D. Sivakumar: Em conjuntos comparáveis ​​de associação. J. Comput. Syst. Sci. 59 (2): 270-280 (1999).

(2) o argumento acima obviamente não diz nada sobre a complexidade de casos médios de qualquer problema de NP, uma vez que a correção de erros está sendo aplicada em uma instância por instância.

Andy Drucker
fonte
8
O software não me permite começar minha resposta com "Oi Gil", e estou um pouco assustado com esse nível de microgerenciamento.
Andy Drucker
2
Isso ocorre porque sua resposta não deve começar com "Oi Gil". Não é um email pessoal, é uma publicação em um site público. Obviamente, vocês não são os que são alvo disso; são novos usuários que não estão cientes dessas convenções que o software pretende controlar.
Yuval Filmus
1
Minha opinião é que é bom reconhecer quando alguém está escrevendo em resposta à contribuição de outra pessoa. Isso é normal e positivo em muitas configurações online. Tentei fazê-lo da maneira mais breve possível, por endereço pessoal; não vejo nada de errado nisso.
Andy Drucker
2
Boa construção! Eu tenho uma pergunta: seja f a função indicadora de L ', e seja como na pergunta de Gil. Agora, seu argumento mostra que h concorda com f que são palavras de código legais. Mas e quanto a y que não são palavras de código legais?
Ou Meir
2
f