Complexidade de circuitos monotônicos de funções de computação em entradas esparsas

O peso de uma cadeia binária é o número de unidades na cadeia. O que acontece se estivermos interessados em calcular uma função monótona em entradas com poucas? $|x|$ $x\in\{0,1\}^n$

Sabemos que decidir se um gráfico possui uma classe é difícil para circuitos monótonos (ver, entre outros, Alon Boppana, 1987), mas se um gráfico tem, por exemplo, no máximo arestas, é possível encontrar um circuito monotônico de profundidade limitada de tamanho que decide -clique. $k$ $k^3$ $f(k)\cdot n^{O(1)}$ $k$

Minha pergunta: existe alguma função difícil de calcular por um circuito monótono, mesmo em entradas com peso menor que ? Aqui, duro significa o tamanho do circuito . $k$ $n^{{k}^{\Omega(1)}}$

Melhor ainda: existe uma função monótona explícita que é difícil de calcular, mesmo que apenas nos importemos com entradas de peso e ? $k_1$ $k_2$

Emil Jeřábek já observou que os limites inferiores conhecidos são válidos para circuitos monótonos que separam duas classes de entradas ( gráficos -cliques versus máximos ), portanto, a custo de alguma independência no argumento probabilístico, é possível torná-lo trabalhar para duas classes de entrada de peso fixo. Isso faria com que fosse uma função de que eu quero evitar. $a$ $(a-1)$ $k_2$ $n$

O que realmente gostaria é uma função explícita e difícil para e muito menor que (como na estrutura de complexidade parametrizada). Melhor ainda se . $k_1$ $k_2$ $n$ $k_1=k_2+1$

Observe que uma resposta positiva para implicaria um limite inferior exponencial para circuitos arbitrários. $k_1=k_2$

Atualização : Esta pergunta pode ser parcialmente relevante.

cc.complexity-theory lower-bounds circuit-complexity parameterized-complexity monotone MassimoLauria
fonte

À sua primeira pergunta (geral) (não sobre o Clique). Eu acho que mesmo o caso de entradas com no máximo

é muito difícil. Faça um gráfico

bipartido

com

. Atribua a cada vértice

uma variável booleana

. Seja

2

$2$

n \times m

$n\times m$

G

$G$

m = o (n)

$m=o(n)$

u

$u$

x_{u}

$x_u$

ser uma função monótona booleano cujos termos completos são

para as bordas

. Vamos

f_{G} (x)

$f_G(x)$

x_{u} \land x_{v}

$x_u\land x_v$

u v

$uv$

G

$G$

seja o tamanho mínimo de um circuito monótono que calcule corretamente

em entradas com

unidades. Então, qualquer limite inferior

para uma constante

implicaria umlimite inferiorexponencialparacircuitosnão monotônicos.

s (G)

$s(G)$

f_{G}

$f_G$

\leq 2

$\leq 2$

s (G) \geq (2 + c) n

$s(G)\geq (2+c)n$

c > 0

$c>0$

Stasys

Os argumentos existentes para circuitos monótonos precisam que muitas entradas com muitas (

) sejam rejeitadas . O melhor que podemos fazer até agora é provar que

≫ n / 2

$\gg n/2$

um limite inferior quando o circuito tem de aceitar todos os

-cliques, e rejeitar todos os completos

-partite gráficos (

). Btw importante é que você lida comesparsas, não comentradasdensas. Diga,

\exp (min {a, n / b}^{1 / 4})

$\exp(\min\{a,n/b\}^{1/4})$

b

$b$

a

$a$

a < b

$a<b$

k

$k$ -Clique requer circuitos monotônicos de tamanho cerca de

para cada constante

, mas

-Clique possui circuitos monotônicos de tamanho

para cada constante

n^{k}

$n^k$

k \geq 3

$k\geq 3$

(n - k)

$(n-k)$

O (n^{2} \log n)

$O(n^2\log n)$

k

$k$

Stasys

Devo esclarecer que me preocupo com entradas esparsas no sentido de gráfico esparso. A procura de uma classe

em um gráfico muito esparso (com, digamos,

arestas) pode ser feita no tamanho do circuito monotônico FPT.

k

$k$

k^{10}

$k^{10}$

MassimoLauria

Seu exemplo no primeiro comentário é muito bom. Se bem entendi, esse é um problema semelhante com as funções monótonas que são difíceis para um peso fixo

. Usando funções de pseudo complemento para simular entradas negadas, a complexidade do circuito não difere entre maiúsculas e minúsculas e não monótonas. Para

constante (ou pequeno), esse pseudo complemento pode ser implementado com eficiência por um circuito monótono.

k

$k$

k

$k$

MassimoLauria 8/12/11

meu primeiro comentário contou com a complexidade do gráfico. O fenômeno "

" pode ser encontrado na página 13 deste rascunho . Aliás, eu não entendi direito o que você quer dizer com "difícil para kek + 1"? (A culpa é minha, é claro.)

(2 + c) n

$(2+c)n$

Stasys

Considerando especificamente uma parte da questão (por exemplo, para = 1, = 2), Lokam estudou as funções de "duas fatias" neste documento e prova que limites mais baixos podem ser generalizados, portanto, isso é muito difícil. problema aberto relacionado à separação de classes de complexidade básica e qualquer construção / função explícita seria um avanço; do resumo: $k_1$ $k_2$

Uma função booleana f é chamada de função de 2 fatias se for avaliada como zero em entradas com menos de dois 1s e for avaliada como uma em entradas com mais de dois 1s. Nas entradas com exatamente dois 1's f pode ser definido de forma não trivial. Existe uma correspondência natural entre funções de 2 fatias e gráficos. Usando a estrutura de complexidade de gráficos, mostramos que limites inferiores monotônicos superlineares suficientemente fortes para a classe muito especial de funções de 2 fatias implicariam limites inferiores superpolinomiais sobre uma base completa para determinadas funções derivadas deles.

Complexidade do gráfico e funções das fatias / Satyanarayana V. Lokam, Theory Comput. Systems 36, 71–88 (2003)

também como em seus comentários, SJ aborda esse caso semelhante em seu livro na seção que explora a complexidade estelar dos gráficos sec1.7.2.

Complexidade da função booleana: avanços e fronteiras , Stasys Jukna

vzn
fonte

Complexidade de circuitos monotônicos de funções de computação em entradas esparsas

Respostas: