Les ordinateurs quantiques sont très bons pour échantillonner des distributions que nous ne savons pas échantillonner en utilisant des ordinateurs classiques. Par exemple, si f est une fonction booléenne (de à - 1 , 1 ) qui peut être calculée en temps polynomial, alors avec des ordinateurs...
Je m'intéresse au problème d'emballer des copies identiques de rectangles (2 dimensions) dans un polygone convexe (2 dimensions) sans chevauchements. Dans mon problème, vous n'êtes pas autorisé à faire pivoter les rectangles et pouvez supposer qu'ils sont orientés parallèlement aux axes. On vous...
Cette question a été migrée à partir de la validation croisée car elle peut être répondue sur l'échange théorique de pile informatique. Migré il y a 8 ans . J'ai un problème assez unique à résoudre et j'espère que quelqu'un ici pourra me donner un aperçu de la meilleure façon de le résoudre....
Le problème Not All Equal -SAT (NAE k -SAT), étant donné un ensemble C de clauses sur un ensemble X de variables booléennes telles que chaque clause contient au plus k littéraux, demande s'il existe une affectation de vérité des variables telles que chaque clause contient au moins un vrai et au...
Dans l'état actuel des choses, cette question ne convient pas à notre format de questions / réponses. Nous nous attendons à ce que les réponses soient étayées par des faits, des références ou une expertise, mais cette question suscitera probablement un débat, des arguments, des sondages ou une...
Quelqu'un peut-il suggérer une bonne et récente enquête sur le comptage des problèmes et / ou des problèmes qui sont #P.
Je me demandais quels outils les gens de ce domaine (informatique théorique) utilisent pour créer des présentations. Puisqu'une grande partie de l'informatique ne consiste pas seulement à rédiger des articles mais aussi à faire des présentations, j'ai pensé que ce serait une question souple...
Inspiré par les vastes hiérarchies présentes dans la théorie de la complexité, je me suis demandé si de telles hiérarchies étaient également présentes pour les systèmes de types. Cependant, les deux exemples que j'ai trouvés jusqu'à présent ressemblent davantage à des listes de contrôle (avec des...
Je reçois récemment mes articles rejetés des revues (c.-à-d., TALG) sur la simple base de ne pas avoir une différence significative entre la version du journal et des actes (c.-à-d., SODA). La principale raison pour laquelle je soumets à une revue est son processus d'examen approfondi. En dehors de...
Pratiquement, pour un langage qui peut éventuellement être compilé / transformé en instructions au niveau du système, est-il nécessaire que ce soit une grammaire sans contexte? ex: tous les langages de programmation / script sont-ils des grammaires sans contexte? Java est basé sur des CFG, mais...
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...
Considérons un corps convexe centré à l'origine et symétrique (ie si alors ). Je souhaite trouver un corps convexe différent tel que et la mesure suivante soit minimisée:KKKx∈Kx∈Kx\in K−x∈K−x∈K-x\in KLLLK⊆LK⊆LK\subseteq L xf(L)=E(xT⋅x−−−−−√)f(L)=E(xT⋅x)f(L)=\mathbb{E}(\sqrt{x^T \cdot x}) , où est...
Inspiré par cette question , quels sont les problèmes majeurs et les solutions existantes qui nécessitent une amélioration dans le domaine des systèmes distribués (théoriques). Quelque chose comme les protocoles d'adhésion, la cohérence des
J'essaie de trouver à quel point et sont vraiment proches , quand et est une constante ne dépendant pas de n (donc ). Mon estimation est que whp, mais je n'ai pas pu le prouver.E [ t w ( G ) ] G ∈ G ( n , p = c / n ) c > 1 E [ t w ( G ) ] = Θ ( n ) t w ( G ) ≤ E [ t w ( G ) ] + o ( n )t w ( G...
Dans l'informatique quantique, nous nous intéressons souvent aux cas où le groupe d'opérateurs unitaires spéciaux, G, pour un système d-dimensionnel donne exactement tout le groupe SU (d) ou même juste une approximation fournie par une couverture dense de SU (d). Un groupe d'ordre fini, tel que le...
Le problème d'arrêt indique qu'il est impossible d'écrire un programme qui peut déterminer si un autre programme s'arrête, pour tous les programmes d'entrée possibles . Je peux, cependant, certainement écrire un programme qui peut calculer le temps d'exécution d'un programme comme: for(i=0; i<N;...
Nous savons que l'ensemble indépendant maximum (MIS) est difficile à estimer dans un facteur pour tout ϵ >n1−ϵn1−ϵn^{1-\epsilon} moins que P = NP. Quelles sont certaines classes spéciales de graphiques pour lesquelles de meilleurs algorithmes d'approximation sont connus?ϵ>0ϵ>0\epsilon > 0...
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...
Étant donné un ensemble SSS de personnes, je voudrais les asseoir pour une séquence de repas à des tables de taille kkk . (Bien sûr, il y a suffisamment de tables pour asseoir tous les |S||S||S| pour chaque repas.) J'aimerais organiser cela de telle sorte que personne ne partage une table avec la...