Discussion : J'ai passé un peu de temps récemment à apprendre différentes choses sur la complexité de la communication. Par exemple, je me suis familiarisé avec le chapitre pertinent d'Arora / Barak, j'ai commencé à lire certains articles et commandé le livre de Kushilevitz / Nisan. Intuitivement,...
Le graphe linéaire d'un hypergraphe est le graphe (simple) G ayant des arêtes de H comme sommets avec deux arêtes de H adjacentes à G si elles ont une intersection non vide. Un hypergraphe est un r -hypergraphe si chacune de ses arêtes a au plus r sommets.HHHGGGHHHHHHGGGrrrrrr Quelle est la...
L'apparence apparemment inutile de l'extraction de crypto-monnaie a soulevé la question d'alternatives utiles, voir ces questions sur Bitcoin , CST , MO . Je me demande s'il existe un algorithme qui peut convertir pratiquement n'importe quel défi de calcul CC\mathcal C (dont la solution peut être...
À quelle vitesse un algorithme non déterministe pour un problème EXPTIME complet devrait-il impliquer P ≠ N PP≠NPP \neq NP ? Un temps polynomial algorithme non déterministe impliquerait immédiatement parce que P ≠ E X P T I M EP≠EXPTIMEP \neq EXPTIME mais personne ne croit N P = E X P T I M...
Dans cette question , nous semblons avoir identifié un problème naturel qui est NP-complet sous des réductions aléatoires, mais peut-être pas sous des réductions déterministes (bien que cela dépende des hypothèses non prouvées dans la théorie des nombres qui sont vraies). Existe-t-il d'autres...
Le problème intéressant suivant est apparu récemment dans mes recherches: INSTANCE: Graphique .G ( V, E)G(V,E)G(V, E) SOLUTION: un achèvement de cycle impair sans corde, défini comme un surensemble de l'ensemble de bords E de sorte que le graphe complété G ' ( V , E ' ) a la propriété que chaque...
Il est bien connu que les palindromes peuvent être reconnus en temps linéaire sur des machines de Turing à bandes, mais pas sur des machines de Turing à bande unique (auquel cas le temps nécessaire est quadratique). L'algorithme de temps linéaire utilise une copie de l'entrée et utilise donc...
Le théorème de Karp – Lipton déclare que si , alors s'effondre en . Par conséquent, en supposant des séparations entre et , aucun problème complet n'appartiendra à .P H Σ P 2 Σ P 2 Σ P 3 N P P / p o l yN P ⊂ P / p o l yNP⊂P/poly\mathsf{NP} \subset \mathsf{P/poly}P
Rappelons le nombre de nombres premiers est la fonction de décompte des nombres premiers . Par "PRIMES in P", le calcul est en #P. Le problème # P-est-il complet? Ou, peut-être, il y a une raison complexe de croire que ce problème n'est pas # P-complet? π(n)π(n)\pi(n)≤n≤n\le nπ ( n )π(n)π(n)\pi(n)...
Prédire la bourse est difficile! TCS peut-il rendre ce sentiment plus formel? Récemment, j'ai commencé à réfléchir un peu à la finance et je me demandais en quoi la connaissance du TCS pouvait aider. Les fonds spéculatifs et les sociétés d'investissement semblent utiliser le trading algorithmique,...
Selon un récit historique (non vérifié), Kolmogorov pensait que chaque langue dans a une complexité de circuit linéaire. (Voir la question précédente de la conjecture de Kolmogorov selon laquelle a des circuits de taille linéaire .) Notez que cela implique .PP\mathsf{P}PPPP≠NPP≠NP\mathsf{P}\neq...
Laissez un entier fonction d'une valeur telle que 2 F est en # P . S'ensuit-il que F est en # P ? Y a-t-il des raisons de croire qu'il est peu probable que cela tienne toujours? Des références que je devrais connaître?FFF2F2F2F#P#P\#PFFF#P#P\#P De façon assez surprenante, cette situation est...
Actuellement, le calcul des réels dans les langages les plus populaires se fait toujours via des opérations en virgule flottante. D'un autre côté, des théories comme l'effectivité de type deux (TTE) et la théorie des domaines promettent depuis longtemps le calcul exact des réels. De toute évidence,...
La parité et sont comme des jumeaux inséparables. Ou du moins, cela semble au cours des 30 dernières années. À la lumière du résultat de Ryan, il y aura un regain d'intérêt pour les petites classes.AC0AC0AC^0 Furst Saxe Sipser à Yao à Hastad sont toutes des restrictions de parité et aléatoires....
Y a-t-il des références qui fournissent des détails sur les limites inférieures du circuit pour des problèmes difficiles spécifiques survenant en cryptographie tels que l'affacturage entier, problème de logarithme discret premier / composite et sa variante sur un groupe de points de courbes...
Je suis intéressé par la complexité de la résolution d'équations linéaires modulo k , pour k arbitraire (et avec un intérêt particulier pour les puissances premières), en particulier: Problème. Pour un système donné de équations linéaires dans n modules inconnus k , existe-t-il des...
EDIT au 2011/02/08: Après avoir trouvé et lu des références, j'ai décidé de séparer la question d'origine en deux questions distinctes. Voici la partie concernant UP vs NP, pour la partie classes syntaxiques et sémantiques, veuillez consulter Avantages pour les classes syntaxiques et sémantiques ....
Je suis actuellement intéressé à obtenir (ou construire) et à étudier des formules 3-CNF insatisfaisantes et de taille minimale. Autrement dit, elles doivent être constituées du moins de clauses (m = 8 de préférence) et de autant de variables distinctes (n = 4 ou plus) que possible, de sorte que la...
Mon théorème préféré en théorie de la complexité est le théorème de la hiérarchie temporelle. Cependant, cela a été fait en 1965. Je voulais alors savoir s'il y avait quelque chose de similaire pour l'informatique quantique. Si ce n'est pas le cas, quelles sont les personnes / groupes qui...
USTCONN est le problème qui nécessite de décider s'il existe un chemin entre le sommet source et le sommet cible t dans un graphique G , où ils sont tous donnés dans le cadre de l'entrée.ssstttGGG Omer Reingold a montré que USTCONN est en L (doi: 10.1145 / 1391289.1391291 ). La preuve construit un...