Barreiras e complexidade de circuitos monótonos

15

As provas naturais são uma barreira para provar limites inferiores na complexidade do circuito das funções booleanas. Eles não implicam diretamente tal barreira na comprovação de limites mais baixos na complexidade do circuito . Existe algum progresso para identificar essas barreiras? Existem outras barreiras no cenário monótono?monotone

Shiva Kintali
fonte
2
Dick Lipton não escreveu um post sobre isso há alguns meses ao discutir provas naturais? (atualização): aqui está o link: rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs
Suresh Venkat
4
Existem limites inferiores exponenciais conhecidos em circuitos monótonos (Razborov 85, Alon+Boppana 87).
Iddo Tzameret
2
Raz e McKenzie não separaram toda a hierarquia monótona do NC? (R. Raz, P. McKenzie, "Separação da hierarquia monótona do NC")
Michaël Cadilhac
11
Uma questão relacionada: cstheory.stackexchange.com/questions/2291/…
Gil Kalai
7
((Não use para colocar em itálico; use itálico !)) #mumath
297 Jeff Jeff

Respostas:

15

ω(nk/(registron)k)O(nk)

ω(nk/4)

Portanto, a barreira de provas naturais parece não se aplicar à complexidade de circuitos monótonos.

Norbert Blum discutiu por que os limites mais baixos para circuitos monótonos são essencialmente diferentes dos circuitos com negações. A observação principal de Éva Tardos é que uma pequena modificação da função teta de Lovász tem complexidade exponencial de circuitos monótonos.

András Salamon
fonte
11
Também achei "Em provar limites inferiores para o tamanho do circuito" de Karchmer útil para entender por que os circuitos monótonos são diferentes dos circuitos com negação.
Kaveh
11

O ponto recebe uma função booleana geral f; existe uma função booleana monótona g, de modo que qualquer limite inferior super linear em g implica um em f. Ou mais forte, a complexidade geral de f é igual à complexidade monótona de g até O (n).

Ainda não tenho certeza de como isso se relaciona com as barreiras.

pau lipton
fonte
18
Bem-vindo ao TCS SE !! Muito obrigado às suas postagens no blog, é realmente um prazer ler!
Hsien-Chih Chang,