Je voudrais demander des suggestions de bons textes qui introduisent la complexité du circuit. Des indications sur les avancées récentes et les problèmes ouverts dans ce domaine seraient également
Dans la complexité du circuit, nous avons des séparations entre les puissances des différents modèles de circuits. Dans la complexité de la preuve, nous avons des séparations entre les puissances des différents systèmes de preuve. Mais dans l'algorithmique, nous n'avons encore que peu de...
La complexité de l'information a été un outil très utile dans la complexité de la communication, principalement utilisée pour réduire la complexité de la communication des problèmes distribués. Existe-t-il un analogue de la complexité des informations pour la complexité des requêtes? Il existe de...
Ou avec d'autres mots, avons-nous cela pour chaque langue et , ou ?UNEUNEABBBA ≤pBUNE≤pBA \leq_p BB ≤pUNEB≤pUNEB \leq_p
En lisant l'article " Une théorie applicative pour la FPH ", vous pouvez rencontrer le passage suivant: Compte tenu des théories qui caractérisent les classes de complexité informatique, il existe trois approches différentes: dans l'un, les fonctions qui peuvent être définies dans la théorie sont...
J'ai un polytope PPP défini par {x:Ax≤b,x≥0}{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} . Question: Étant donné un sommet vvv de PPP , existe-t-il un algorithme polynomial de temps pour échantillonner uniformément à partir des voisins de vvv dans le graphique de PPP ? (Polynôme dans la dimension, le...
Comme tout le monde le sait, le célèbre livre de Garey et Johnson (et bien d'autres) fournit une excellente référence pour la technique de réduction en milieu classique. Existe-t-il des enquêtes ou des livres sur le thème de la technique de réduction dans l'algorithme paramétré, disons la réduction...
Chaque circuit arithmétique monotone , c'est-à-dire un circuit { + , × }{+,×}\{+,\times\} , calcule un polynôme multivarié avec des coefficients entiers non négatifs. Étant donné un polynôme , le circuitf ( x 1 , … , x n )F( x1, … , Xn)F(X1,…,Xn)F(x_1,\ldots,x_n)F( x1, … ,...
Quand on nous donne une décomposition arborescente d'un graphe de largeur , il y a plusieurs façons de le rendre "agréable". En particulier, il est connu qu'il est possible de le transformer en une décomposition d'arbre où l'arbre est binaire et sa hauteur est . Ceci peut être réalisé tout en...
Cette question concerne la logique propositionnelle et toutes les occurrences de «résolution» doivent être lues comme «résolution propositionnelle». Cette question est quelque chose d'extrêmement basique mais cela me dérange depuis un moment. Je vois des gens affirmer que la résolution...
Existe-t-il un algorithme de réarrangement temporel sur place linéaire? C'est l'algorithme que certaines mains particulièrement habiles sont capables d'exécuter: diviser uniformément un tableau d'entrée de taille égale, puis entrelacer les éléments des deux moitiés. Mathworld a une brève page sur...
Étant donné une matrice (en supposant ), quel est l'algorithme le plus rapide pour calculer son rang et sa base des colonnes?m × nm×nm \times nm ≥ nm≥nm \ge n Je suis conscient qu'il peut être résolu par intersection matroïde linéaire, ce qui implique un algorithme déterministe temporel et un...
Que se passe-t-il si nous définissons telle sorte qu'au lieu d'un circuit Turing-machine / polysize polytime, une machine Turing espace journal ou un circuit code le problème?P P A DPPAD{\bf PPAD} A C 0AC0{\bf AC^0} Donner récemment des algorithmes plus rapides pour la satisfiabilité des circuits...
Le problème de maintenance des commandes (ou «maintien de l'ordre dans une liste») est de supporter les opérations: singleton: crée une liste avec un élément, lui renvoie un pointeur insertAfter: donné un pointeur sur un élément, insère un nouvel élément après, renvoyant un pointeur sur le nouvel...
Contexte Une formule à lecture unique sur un ensemble de portes (également appelée base) est une formule dans laquelle chaque variable d'entrée apparaît une fois. Les formules à lecture unique sont communément étudiées sur la base de De Morgan (qui a les portes 2 bits ET et OU, et la porte 1 bit...
Le problème #SAT est le problème canonique # P-complete. C'est un problème de fonction plutôt qu'un problème de décision. Il demande, étant donné une formule booléenne dans la logique propositionnelle, combien d'affectations satisfaisantes F a. Quelles sont les meilleures limites inférieures sur...
Étant donné deux CNF, s'ils ont le même nombre d'affectations pour les rendre vraies, répondez "Oui", sinon répondez "Non". Il est facile de voir que c'est dans , car si nous connaissons le nombre exact de solutions à ces deux CNF, nous les campons simplement et répondons "Oui" ou...
Dans leur article Approximate Distance Oracles , Thorup et Zwick ont montré que pour tout graphique non orienté pondéré, il est possible de construire une structure de données de taille qui peut renvoyer une ( 2 k - 1 ) approximative distance entre n'importe quelle paire de sommets dans le...
Connaît-on des résultats qui excluent l'existence de structures de données «trop belles pour être vraies»? Par exemple: peut-on ajouter des fonctionnalités et J o i n à une structure de données de maintenance de commande (voir Dietz et Sleator STOC '87 ) tout en obtenant des opérations de temps O (...
Résultat 1: le théorème de Linial-Mansour-Nisan dit que le poids de Fourier des fonctions calculées par les circuits A C0UNEC0\mathsf{AC}^0 est concentré sur les sous-ensembles de petite taille à forte probabilité. Résultat 2: Le a son poids de Fourier concentré sur le coefficient du degré n .P A R...