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...
Dans la théorie de l'information quantique, la distance entre deux canaux quantiques est souvent mesurée en utilisant la norme du diamant. Il existe également un certain nombre de façons de mesurer la distance entre deux états quantiques, comme la distance de trace, la fidélité, etc. L'...
Soit le pire temps d'exécution d'un problème sur une entrée de taille n . Faisons un peu bizarre le problème en fixant f ( n ) = n 2 pour n = 2 k mais f ( n ) = n pour n = 2 kf(n)f(n)f(n)nnnf(n)=n2f(n)=n2f(n) = n^2n=2kn=2kn=2kf(n)=nf(n)=nf(n) = n .n=2k+1n=2k+1n=2k+1 Alors, quelle est la limite...
Il semble connu que pour trouver une réponse à une requête sur une base de données relationnelle D , il faut du temps | D | | Q | , et on ne peut pas se débarrasser de l'exposant | Q | .QQQDDD|D||Q||D||Q||D|^{|Q|}|Q||Q||Q| Comme peut être très volumineux, nous nous demandons pourquoi les bases de...
Je m'intéresse aux modèles de graphes aléatoires similaires aux graphes de vrais réseaux informatiques. Je ne sais pas si le modèle commun bien étudié ( n sommets, chaque bord possible est sélectionné avec la probabilité p ) est bon pour étudier les réseaux informatiques réels...
L'informatique réversible est un modèle informatique qui ne permet que des opérations thermodynamiquement réversibles. Selon le principe de Landauer, qui stipule que l'effacement d'un peu d'informations libère joules de chaleur, cela exclut les fonctions de transition qui ne sont pas un à un (par...
Dans leur article (p. 503) Garey et Johnson remarquent: ... il pourrait exister un problème NP-complet qui n'est ni NP-complet au sens fort ni résoluble par un algorithme pseudo-polynomial temporel ... Quelqu'un connaît-il des problèmes avec les propriétés mentionnées ci-dessus? Je pense que la...
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...
Quelles sont les meilleures ressources pour trouver des offres d'emploi pour des postes de professeurs en théorie CS? Existe-t-il un site Web ou une liste de diffusion en particulier assez complet? J'ai actuellement l'impression qu'il faut utiliser une variété de ressources pour obtenir une liste...
Considérez équipé du produit scalaire standard et vecteurs: . Nous voulons construire une structure de données qui autorise les requêtes au format suivant: étant donné output . Est-il possible d'aller au-delà du temps de requête O (nm) trivial ? Par exemple, si n = 2 , alors il est immédiat...
La question est simple et directe: pour un fixe nnn, combien de langues (différentes) sont acceptées par un DFA de taille nnn (c'est-à-dire nnn états)? Je vais déclarer officiellement ceci: Définissez un DFA comme ( Q , Σ , δ, q0, F)(Q,Σ,δ,q0,F)(Q,\Sigma,\delta,q_0,F) , où tout est comme d'habitude...
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,...
Contexte: Chao Xu a posté il y a quelque temps la question suivante: " Existe-t-il des algorithmes de tri de comparaison connus qui ne se réduisent pas à des réseaux de tri, de sorte que chaque élément est comparé fois?O ( logn)O(Journaln)O(\log n) ". Il semble que nous soyons un peu coincés avec...
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...
Le calcul de la constante de Cheeger d'un graphique , également connu sous le nom de constante isopérimétrique (car il s'agit essentiellement d'un rapport surface / volume minimum), est connu pour être NP-complet. Elle est généralement approximative. Je voudrais savoir si des algorithmes...
Soit un graphe non orienté non pondéré avec sommets et arêtes. Est-il possible de prétraiter et de produire une structure de données de taille afin qu'il puisse répondre aux requêtes de la forme "distance entre et " dans le temps O (n)?n m G m ⋅ p o l y l o g ( n ) u vgGGnnnmmmgGGm ⋅ p o l y l o g...
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...
Supposons que nous ayons un graphique pondéré non orienté (avec des poids non négatifs). Supposons que tous les chemins les plus courts dans G soient uniques. Supposons que nous ayons ces chemins (séquences d'arêtes non pondérées), mais ne connaissons pas lui-même. Pouvons-nous produire un qui...
Je venais tout juste d'avoir une discussion sur les machines de Turing quand on m'a demandé: "La machine de Turing dérive-t-elle d'automates, ou est-ce l'inverse"? Je ne connaissais pas la réponse bien sûr, mais je suis curieux de le savoir. La machine de Turing est fondamentalement une version...
On vous donne un graphe avec n sommets. Il peut être bipartite si vous le souhaitez. Il existe m ensembles d'arêtes E 1 , … , E m ⊆ E (disons disjoints). Je m'intéresse au problème de trouver un sous-ensemble S ⊆ V , aussi petit que possible (ou même plus petit), tel que le graphe induit G S ait au...