Quels problèmes

Le célèbre Picture of The World de Neil Immerman est le suivant (cliquez pour agrandir):

Sa classe "Vraiment faisable" ne comprend aucune autre classe; ma question est alors:

Qu'est-ce qu'un problème AC ⁰ considéré comme peu pratique et pourquoi?

cc.complexity-theory circuit-complexity Michaël Cadilhac
la source

Peut-être un problème qui nécessite des circuits de profondeur 10 ^ {10 ^ 100}?

Tsuyoshi Ito du

@ Ross: Je ne le pense pas car il n'a pas mentionné «monde réel» et il a demandé «pourquoi»; Je pense que mon commentaire précédent répond au moins à la partie «pourquoi». Cependant, il est vrai que je n'ai pas d'exemple de problèmes «naturels» qui sont en AC0 et nécessitent des circuits de profondeur 10 ^ {10 ^ 100}.

Tsuyoshi Ito

Il existe de nombreux problèmes du monde réel intéressants qui pourraient être résolus en temps constant et en espace constant (dans pratiquement tous les modèles de calcul), mais les gens ont maintenant une idée de la façon de les résoudre dans la pratique. Des exemples extrêmes calculent certaines constantes; nous pourrions coder en dur la bonne réponse (par exemple, 0 ou 1), mais nous ne connaissons pas encore la réponse.

Jukka Suomela

Jukka: ce sont des exemples de problèmes. Les équations diophantiennes (comme celles de Fermat) sont indécidables en tant que classe, même si les instances individuelles que nous avons décidées ont en réalité des circuits à profondeur constante.

András Salamon

@ András: Si vous préférez les problèmes de décision avec une infinité d'instances "oui" et "non": Soit

composé de tous les nombres pairs et

, où

si le joueur blanc a une stratégie gagnante aux échecs et sinon

. Curieusement, il existe une famille de circuits très simple qui décide de

, mais je dirais quand même que c'est "peu pratique". Non pas parce que le circuit serait énorme, mais parce que la conception du circuit serait un énorme effort de calcul ... Tricher? -)

L

$L$

x

$x$

x = 1

$x = 1$

x = 3

$x = 3$

L

$L$

Jukka Suomela

Réponses:

Si vous voulez un exemple de fonction AC ⁰ qui nécessite une profondeur et ne peut pas être calculée par des circuits AC ⁰ de profondeur , essayez les fonctions Sipser . L'exposant est la profondeur nécessaire pour un circuit AC ^{0 de} taille polynomiale . Avec une profondeur , le circuit aurait besoin exponentiellement de nombreuses portes. $d$ $d-1$ $S^{d,n}$ $d$ $d-1$

Donc, calculer pour ne serait pas "vraiment faisable". $S^{d,n}$ $d = 10^{10^{100}}$

EDIT: Votre question demande également pourquoi cela ne serait pas possible. Je suppose que la raison en est que est plus que le nombre d'atomes dans l'univers visible. $10^{10^{100}}$

Robin Kothari
la source

C'est bien merci! Peut-être pouvez-vous ajouter une définition informelle des fonctions Sipser? Je ne connaissais pas ce nom.

Michaël Cadilhac

@ Michaël: Malheureusement, je n'ai pas une bonne définition intuitive des fonctions Sipser. L'idée est de faire une fonction de d quantificateurs telle qu'aucun circuit de profondeur d-1 ne puisse le calculer. Nous voulons donc que les quantificateurs d se quantifient sur un très grand nombre de variables. Il y a un bel article d'Iddo Tzameret, intitulé "La séparation de Håstad des circuits à profondeur constante utilisant les fonctions Sipser" ( itcs.tsinghua.edu.cn/~tzameret/SipserSwitching.pdf ) qui définit formellement les fonctions à la page 7.

Robin Kothari

Toute cette hiérarchie est intentionnellement robuste sous des changements polynomiaux de la taille d'entrée. Toute classe qu'elle contient peut donc contenir des fonctions dont la complexité est disons n ^ {1000000000} qui seraient théoriquement "réalisables" mais certainement pas pratiquement. Cependant, il s'agira très probablement de problèmes très artificiels. En particulier par un argument de comptage, il existe une famille de formules DNF (= AC ^ 0 profondeur 2 circuits) de taille n ^ 1000000 qu'aucun algorithme dont le temps d'exécution est inférieur à n ^ 999999 ne peut calculer. (Dans un cadre uniforme, nous attendons quelque chose de similaire, mais ne pouvons pas le prouver.)

Noam
la source

Le problème d'arrêt lorsque l'entrée est représentée en unaire est en AC ^ 0 et pourtant tout à fait irréalisable en réalité. Je ne suis pas sûr que ce soit ce que vous vouliez dire, mais cela pourrait être ce que voulait dire Immerman.

Elad
la source

Je suppose que les classes dans le diagramme sont définies avec une notion d'uniformité? Sinon, la direction vers le haut ne représenterait pas le confinement, car P ne contient pas AC ^ 0 non uniforme.

Robin Kothari

A C^{0}

$AC^0$

{0, 1}

$\{0,1\}$

{0, m a x; X, B I T, \leq, =}

$\{0,max; X,BIT,\le,=\}$

X

$X$

Point bien pris. Comme alternative, après Erdos, on pourrait plutôt suggérer le problème que pour toute entrée, sort le nombre Ramsey pour le rouge six et le bleu six.

Elad