Dans le modèle à boîte noire, le problème de la détermination de la sortie d'une machine BPP sur l'entrée est le problème de comptage approximatif de la détermination de avec une erreur additive 1/3 (disons).x E r M ( x , r )M(x,r)M(x,r)M(x,r)xxxErM(x,r)ErM(x,r)E_r M(x,r) Existe-t-il un problème...
Je veux savoir si la non-uniformité aide les fonctions informatiques dans la pratique. Il est facile de montrer qu'il existe des fonctions dans , de prendre n'importe quelle fonction non calculable f et de considérer le langage { 0 f ( n ) : n ∈ ω }, qui a clairement des circuits non uniformes...
C'est peut-être une question fondamentale, mais j'ai lu et essayé de comprendre des articles sur des sujets tels que le calcul de l'équilibre de Nash et les tests de dégénérescence linéaire et je ne savais pas comment les nombres réels sont spécifiés en entrée. Par exemple, quand il est indiqué que...
Je viens d'enseigner l' algorithme de raccourci aléatoire de Karger-Stein dans ma classe d'algorithmes diplômés. C'est un vrai bijou algorithmique , donc je ne peux pas ne pas l' enseigner, mais cela me laisse toujours frustré, car je ne connais pas d'autres applications de la technique principale....
Si est un graphe irrégulier d non orienté et S est un sous-ensemble des sommets de cardinalité ≤ | V | / 2 , appelez l' expansion de bord de S la quantitéG = ( V, E)G=(V,E)G=(V,E)réddSSS≤ | V| / 2≤|V|/2\leq |V|/2SSS ϕ ( S) : = Erége s ( S, V- S)ré⋅ | S| ⋅ | V- S|ϕ(S):=Edges(S,V−S)d⋅|S|⋅|V−S|\phi(S)...
Peter Shor a montré que deux des problèmes NP-intermédiaires les plus importants, l'affacturage et le problème de log discret, sont en BQP. En revanche, le meilleur algorithme quantique connu pour SAT (recherche de Grover) ne produit qu'une amélioration quadratique par rapport à l'algorithme...
Que sont les "régions faciles" pour la satisfiabilité? En d'autres termes, des conditions suffisantes pour qu'un solveur SAT puisse trouver une affectation satisfaisante, en supposant qu'elle existe. Un exemple est lorsque chaque clause partage des variables avec quelques autres clauses, en raison...
Je réfléchis au problème suivant depuis un certain temps et je n'ai pas trouvé de solution polynomiale pour cela. Uniquement source brute. J'ai essayé de réduire également un problème NP-Complete sans succès. Voici le problème : Vous avez un ensemble trié de paires d'entiers positifs....
Je suis désolé si cette question est un peu vague, mais je suis curieux de savoir comment les chercheurs qui réussissent obtiennent une "sensation" pour les résultats du TCS. Par exemple, l'algèbre linéaire peut être comprise géométriquement, ou en termes d'interprétations physiques (les vecteurs...
On sait que, étant donné un sous-ensemble à points de ℓ d 2 (c'est-à-dire, étant donné n points dans R d avec une distance euclidienne), il est possible de les incorporer isométriquement dans ℓ ( nnnnℓd2ℓ2d\ell_2^dnnnRdRd{\mathbb R}^d.ℓ(n2)1ℓ1(n2)\ell^{n\choose 2}_1 L'isométrie est-elle calculable...
Je recherche des codes correcteurs d'erreurs du type suivant: codes binaires à débit constant, décodable à partir d'une fraction constante d'erreurs, par un décodeur réalisable en tant que circuit booléen de taille , où est la longueur de codage.O(N)O(N)O(N)NNN Quelques antécédents: Spielman, dans...
J'ai un peu de mal à bien comprendre les dernières étapes de l'algorithme d'affacturage de Shor. Étant donné un NNN nous voulons factoriser, nous choisissons un aléatoire xxxqui a l'ordre rrr . La première étape consiste à mettre en place les registres et à appliquer l'opérateur Hadamard. La...
Je suis un informaticien qui suit un cours sur la topologie (une pincée de topologie ponctuelle fortement aromatisée par la théorie du continuum). Je me suis intéressé aux problèmes de décision en testant une description d'un espace (par simplification) pour les propriétés topologiques; ceux...
À ma grande surprise, je n'ai pas pu trouver de documents à ce sujet - probablement recherché les mauvais mots clés. Donc, nous avons un tableau de tout, et une fonction sur ses indices; f est une permutation.ffffff Comment réorganiser le tableau selon avec une mémoire et une exécution aussi...
Je n'ai pas réussi à trouver cette structure de données, mais je ne suis pas un expert dans le domaine. La structure implémente un ensemble et est essentiellement un tableau d'éléments comparables avec un invariant. L'invariant est le suivant (défini récursivement): Un tableau de longueur 1 est un...
Il est généralement considéré comme peu probable que les ordinateurs quantiques soient capables de résoudre efficacement des problèmes NP-complets. Dans le cas classique, une approche pour résoudre ces problèmes consiste à utiliser des algorithmes d'approximation. Y a-t-il eu des recherches sur les...
Je m'intéresse à des exemples de problèmes où un théorème qui n'a apparemment rien à voir avec la mécanique quantique / l'information (par exemple énonce quelque chose sur des objets purement classiques) peut néanmoins être prouvé en utilisant des outils quantiques. Une enquête Quantum Proofs for...
Quelle est la complexité de décider si un circuit avec bits d'entrée et bits de sortie calcule une permutation de ? en d'autres termes, si chaque chaîne de bits dans est une sortie du circuit pour une entrée? Cela ressemble à un problème qui a été étudié, mais je ne trouve aucune référence. nn{0,1...
Pourquoi les langages réguliers (et à partir de ces expressions régulières) sont-ils appelés "réguliers"? Il y a beaucoup de régularité également dans les langues sans contexte et d'autres types de langues. Je suppose que, au début, l'adjectif "régulier" a été utilisé pour différencier ce type de...
Je suis confus par la subtile différence entre les propositions et les jugements lorsqu'ils sont exposés à la théorie du type intuitionniste. Quelqu'un peut-il m'expliquer à quoi bon les distinguer et qu'est-ce qui les distingue? Surtout au vu de l'isomorphe de