Existe-t-il des problèmes NP-complets pour lesquels un algorithme est connu que le temps d'exécution attendu est polynomial (pour une distribution sensible sur les instances)? Sinon, existe-t-il des problèmes pour lesquels l'existence d'un tel algorithme a été établie? Ou l'existence d'un tel...
Edit: j'ai d'abord mal formulé ma contrainte (2), elle est maintenant corrigée. J'ai également ajouté plus d'informations et d'exemples. Avec certains collègues, étudiant une autre question algorithmique, nous avons pu réduire notre problème au problème intéressant suivant, mais nous n'avons pas pu...
Il est clair que tout problème décidable dans un espace de log déterministe ( LLL ) s'exécute au maximum dans le temps polynomial ( PPP ). Il y a une multitude de classes de complexité entre LLL et PPP . Les exemples incluent NLNLNL , LogCFLLogCFLLogCFL , NCiNCiNC^i , SACiSACiSAC^i , ACiACiAC^i ,...
EDIT (v2): Ajout d'une section à la fin sur ce que je sais du problème. EDIT (v3): Ajout d'une discussion sur le degré de seuil à la fin. Question Cette question est principalement une demande de référence. Je ne connais pas grand-chose au problème. Je veux savoir s'il y a eu des travaux antérieurs...
Il existe une littérature abondante et au moins un très bon livre exposant la dureté connue des résultats d'approximation pour les problèmes NP-difficiles dans le contexte d'erreur multiplicative (par exemple, l'approximation 2 pour la couverture des sommets est optimale en supposant UGC). Cela...
La conjecture des jeux uniques de Subhash Khot est l'un des domaines de recherche actifs en théorie de la complexité. Quelles preuves en avons-nous? Quelles preuves avons-nous contre cela?
Actuellement, Bitcoin dispose d'un système de preuve de travail (PoW) utilisant SHA256. D'autres fonctions de hachage utilisent des graphiques d'utilisation du système de preuve de travail, l'inversion partielle de la fonction de hachage. Est-il possible d'utiliser un problème de décision dans la...
L'accès à un oracle fournirait une accélération super-polynomiale majeure pour tout dans N P - P (en supposant que l'ensemble n'est pas vide). Il est cependant moins clair combien P bénéficierait de cet accès Oracle. Bien sûr, l'accélération dans P ne peut pas être super-polynomiale, mais elle peut...
On sait que le cycle hamiltonien (jambon en abrégé) est NP-complet et que le cycle planaire du jambon est NP-complet. La preuve pour Planar Ham Cycle n'est pas de Ham Cycle. Existe-t-il un joli gadget qui, étant donné un graphe G, remplacera tous les croisements par un gadget plan afin que vous...
Cette question est liée à une réponse que j'ai postée en réponse à une autre question. Le problème des 3 partitions est le problème suivant: Instance : entiers positifs a 1 ,…, a n , où n = 3 m et la somme des n entiers est égale à mB, de sorte que chacun a i satisfait B / 4 <a i <B / 2....
Quelles sont les raisons impérieuses de croire ? L est la classe des algorithmes de l'espace de journal avec des pointeurs vers l'entrée.L≠PL≠PL\neq P Supposons que L = P pour le moment. À quoi ressemblerait un algorithme d'espace de journalisation pour un problème P-complet dans ses grandes...
Il y a clairement une réduction de CLIQUE à k-Color car ils sont tous deux NP-Complete. En fait, je peux en construire un en composant une réduction de CLIQUE à 3-SAT avec une réduction de 3-SAT à k-Color. Je me demande s'il y a une réduction directe raisonnable entre ces problèmes. Disons, une...
Récemment, j'ai vu plusieurs articles sur arxiv qui se réfèrent à un système de preuve appelé somme des carrés. Quelqu'un peut-il expliquer ce qu'est une preuve de somme des carrés et pourquoi ces preuves sont importantes / intéressantes? Comment sont-ils liés à d'autres systèmes de preuve...
La théorie de la complexité, à travers des concepts tels que la complétude NP, fait la distinction entre les problèmes de calcul qui ont des solutions relativement efficaces et ceux qui sont insolubles. La complexité "fine" vise à affiner cette distinction qualitative en un guide quantitatif quant...
Que sait-on de la complexité de trouver des circuits minimaux qui calculent SAT jusqu'à la longueur ? nnn Plus formellement: quelle est la complexité d'une fonction qui, étant donnée en entrée, sort un circuit minimal C tel que pour toute formule φ avec | φ | ≤ n , C ( φ ) = S A T ( φ )...
Motivé par le commentaire de Fortnow sur mon article, Preuve que le problème d'isomorphisme graphique n'est pas completNPNPNP G I N P N P P G I P , et par le fait que est un candidat principal pour le problème intermédiaire (pas complet ni en ), je suis intéressé par des preuves connues que se...
Dans l'enquête "Small Depth Quantum Circuits" de D. Bera, F. Green et S. Homer (p. 36 de ACM SIGACT News, juin 2007 vol. 38, no. 2) , j'ai lu la phrase suivante: La version classique de (dans laquelle les portes et ont un fanout au plus constant) est manifestement plus faible que . A N D O R A C 0Q...
Certains d'entre vous ont peut-être suivi cette question , qui a été fermée en raison d'un niveau de recherche insuffisant. J'extrais donc la partie de la question qui se situe au niveau de la recherche. Au-delà des techniques "plus simples", telles que la réduction au tri ou un problème...
Je sais que trivialement la fonction OR sur nnn variables X1, … , Xnx1,…,xnx_1,\ldots, x_n peut être représentée exactement par le polynôme p ( x1, … , Xn)p(x1,…,xn)p(x_1,\ldots,x_n) comme tel: p ( x1, … , Xn) = 1 - ∏ni = 1( 1 - xje)p(x1,…,xn)=1−∏i=1n(1−xi)p(x_1,\ldots,x_n) = 1-\prod_{i =...
Considérez les problèmes d'optimisation de la forme suivante. Soit une fonction calculable en temps polynomial qui mappe une chaîne en un nombre rationnel. Le problème d'optimisation est le suivant: quelle est la valeur maximale de sur les chaînes à bits ?x f ( x ) n xf(x)f(x)f(x)xxxF( x...