Complexité des circuits monotones des fonctions de calcul sur les entrées clairsemées

Le poidsd'une chaîne binaire est le nombre de uns dans la chaîne. Que se passe-t-il si nous sommes intéressés à calculer une fonction monotone sur des entrées avec quelques-unes? $|x|$ $x\in\{0,1\}^n$

On sait que décider si un graphe a une -clique est difficile pour les circuits monotones (voir entre autres Alon Boppana, 1987), mais si un graphe a par exemple au plus arêtes il est possible de trouver un circuit de profondeur borné monotone de taille qui décide de -clique. $k$ $k^3$ $f(k)\cdot n^{O(1)}$ $k$

Ma question: existe-t-il une fonction difficile à calculer par un circuit monotone même sur des entrées de poids inférieur à ? Ici, hard signifie la taille du circuit . $k$ $n^{{k}^{\Omega(1)}}$

Encore mieux: existe-t-il une fonction monotone explicite qui est difficile à calculer même si nous ne nous soucions que des entrées de poids et ? $k_1$ $k_2$

Emil Jeřábek a déjà observé que les limites inférieures connues sont valables pour les circuits monotones qui séparent deux classes d'entrées ( graphiques -cliques vs graphiques maximaux ), donc au prix d'une certaine indépendance dans l'argument probabiliste, il est possible de le faire travailler pour deux classes d'entrée de poids fixe. Cela ferait que soit une fonction de que je veux éviter. $a$ $(a-1)$ $k_2$ $n$

Ce que l'on aimerait vraiment, c'est une fonction dure explicite pour et beaucoup plus petite que (comme dans le cadre de complexité paramétré). Encore mieux si . $k_1$ $k_2$ $n$ $k_1=k_2+1$

Notez qu'une réponse positive pour impliquerait une borne inférieure exponentielle pour les circuits arbitraires. $k_1=k_2$

Mise à jour : cette question peut être partiellement pertinente.

cc.complexity-theory lower-bounds circuit-complexity parameterized-complexity monotone MassimoLauria
la source

À votre toute première question (générale) (pas sur Clique). Je pense que même le cas des entrées avec au plus entrées est très difficile. Prendre un bipartite graphe avec . Attribuez à chaque sommet une variable booléenne . Laissez soit une voix monotone fonction booléenne dont minterms sont pour les bords de . Soit la taille minimale d'un circuit monotone qui calcule correctement sur les entrées avec uns. Alors toute borne inférieure pour une constante

2

$2$

n \times m

$n\times m$

G

$G$

m = o (n)

$m=o(n)$

u

$u$

x_{u}

$x_u$

f_{G} (x)

$f_G(x)$

x_{u} \land x_{v}

$x_u\land x_v$

u v

$uv$

G

$G$

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$ impliquerait une borne inférieure exponentielle pour les circuits non monotones .

Stasys

Les arguments existants pour les circuits monotones nécessitent que de nombreuses entrées avec plusieurs ( ) soient rejetées . Le mieux que nous pouvons faire à ce jour est de prouver limite inférieure lorsque le circuit doit accepter tous -cliques, et rejeter tous les complets graphiques -partite ( ). Btw est important que vous traitez avec des entrées clairsemées , pas avec des entrées denses . Disons que -Clique nécessite des circuits monotones de taille environ pour chaque constante , mais -Clique a des circuits monotones de taille pour chaque

≫ n / 2

$\gg n/2$

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

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

b

$b$

a

$a$

a < b

$a<b$

k

$k$

n^{k}

$n^k$

k \geq 3

$k\geq 3$

(n - k)

$(n-k)$

O (n^{2} \log n)

$O(n^2\log n)$ constante .

k

$k$

Stasys

Je dois préciser que je me soucie des entrées clairsemées au sens de graphe clairsemé. La recherche d'une -clique dans un graphe très clairsemé (avec par exemple arêtes) peut être effectuée en taille de circuit monotone FPT.

k

$k$

k^{10}

$k^{10}$

MassimoLauria

Votre exemple dans le premier commentaire est très sympa. Si je comprends bien, c'est un problème similaire avec les fonctions monotones qui sont difficiles sur un poids fixe . En utilisant des fonctions pseudo-complémentaires pour simuler des entrées négatives, la complexité du circuit ne diffère pas entre le cas monotone et le cas non monotone. Pour un (ou petit) constant, ce pseudo-complément peut être mis en œuvre efficacement par un circuit monotone.

k

$k$

k

$k$

MassimoLauria

mon premier commentaire s'est appuyé sur la complexité du graphique. Le phénomène " " se trouve à la page 13 de ce projet . Btw je n'ai pas bien compris ce que tu veux dire par "être dur pour k et k + 1"? (Ma faute, bien sûr.)

(2 + c) n

$(2+c)n$

Stasys

considérant spécifiquement une partie de la question (par exemple pour = 1, = 2), Lokam a étudié les fonctions "2 tranches" dans cet article et prouve que des limites inférieures fortes peuvent être généralisées, c'est donc un problème ouvert très difficile liée à la séparation des classes de complexité de base et une telle construction / fonction explicite serait une percée; du résumé: $k_1$ $k_2$

Une fonction booléenne f est appelée fonction à 2 tranches si elle s'évalue à zéro sur les entrées avec moins de deux 1 et s'évalue à une sur les entrées avec plus de deux 1. Sur les entrées avec exactement deux 1, f peut être défini de manière non triviale. Il existe une correspondance naturelle entre les fonctions à 2 tranches et les graphiques. En utilisant le cadre de la complexité du graphe, nous montrons que des bornes inférieures monotones superlinéaires suffisamment fortes pour la classe très spéciale de fonctions à 2 tranches impliqueraient des bornes inférieures superpolynomiales sur une base complète pour certaines fonctions qui en dérivent.

Complexité graphique et fonctions de tranche / Satyanarayana V. Lokam, Theory Comput. Systèmes 36, 71–88 (2003)

comme dans ses commentaires, SJ couvre ce cas similaire dans son livre dans la section explorant la complexité en étoile des graphiques sec1.7.2.

Complexité de la fonction booléenne: avancées et frontières , Stasys Jukna

vzn
la source

Complexité des circuits monotones des fonctions de calcul sur les entrées clairsemées

Réponses: