Une observation simple est que si un problème est décidable par un programme non déterministe polynomial en utilisant O ( log n ) des bits non déterministes ( par exemple, tous les témoins sont logarithmiques de long), alors A ∈ P .AAAO(logn)O(logn)O(\log n)A∈PA∈PA \in \mathsf{P} Si l'on pose...
La densité d'un langage est une fonction définie comme Supposons et sont des langues sur un alphabet fini, grand nombre-un logspace réduit à et ne sont pas dans . Les fonctions sont polynomiales s'il y a des polynômes et tels que pour tout , etXXXdX:N→NdX:N→Nd_X \colon \mathbb{N} \to...
Le théorème de la hiérarchie temporelle stipule que les machines de turing peuvent résoudre plus de problèmes si elles ont (assez) plus de temps. Tient-il d'une manière ou d'une autre si l'espace est limité asymptotiquement? Comment liéDTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n),...
Dans la récente préimpression https://arxiv.org/abs/1801.00776 , il est affirmé que nombres réels peuvent être triés dans le temps et l'espace linéaire. L'article semble raisonnable, même si je ne suis pas un expert en algorithmes de tri.nnnO(nlogn−−−−√),O(nlogn),O(n \sqrt{\log n}), Si elle est...
Il y a un chercheur montrant que l'effacement d'un bit doit consommer de l'énergie, maintenant y a-t-il des recherches sur la consommation moyenne d'énergie d'un algorithme avec une complexité de calcul ? Je suppose que la complexité de calcul F ( n ) est corrélée à la consommation moyenne...
Imaginons que nous ayons deux ensembles mmm de points X,Y⊂RnX,Y⊂RnX,Y\subset \mathbb{R}^n . Quelle est la complexité (temporelle) des tests s'ils diffèrent uniquement par la rotation? : il existe une matrice de rotation OOT=OTO=IOOT=OTO=IOO^T=O^TO=I telle que X=OYX=OYX=OY ? Il y a un problème de...
Je lis la preuve d' ici et je suis tombé sur un problème technique (pourtant crucial). Je sais que c'est assez spécifique et le contexte est problématique, mais je n'ai pas pu le comprendre moi-même. Aux pages 51 et 55, après avoir présenté les vérificateurs "standard", ils se tournent pour...
Étant donné tout graphe simple non orienté G, il n'est pas trivial de déterminer si G a des automorphismes non triviaux (sans identité). Mais quels sont les résultats sur les bornes supérieures / inférieures de ce problème de
Je me demande si les classes NPC définies par plusieurs réductions et les réductions de Turing sont égales. Edit: Une autre question, est-ce que les réductions de Turing ne font que réduire les classes C et co-C pour certains C ou existe-t-il une classe telle qu'il existe un problème qui n'est pas...
Quelle est la complexité temporelle exacte de l' algorithme d'espace de journalisation st-connectivité non orienté d'Omer
Pendant un premier cycle en EE, j'ai assisté à des conférences qui présentaient une belle caractérisation des circuits booléens en termes de nombre de boucles imbriquées. En termes de complexité, les circuits booléens sont souvent considérés comme des creux, mais dans les cycles matériels réels,...
Pour un graphe donné , le problème du séparateur demande s'il existe un ensemble de sommets ou d'arêtes de petite cardinalité (ou poids) dont la suppression divise G en deux graphes disjoints de tailles approximativement égales. C'est ce qu'on appelle le problème du séparateur de sommets lorsque...
Supposons que NP = co-NP et le polynôme délimitent la longueur de la preuve d'insatisfiabilité pour une instance 3-CNF x . Y a-t-il alors des résultats sur la forme que peut prendre une preuve d'insatisfaction pour x de longueur ≤ p ( x ) ? Autrement dit, une telle preuve devrait-elle, par exemple,...
Ce qui suit peut sembler stupide (et cela reflète probablement ma mauvaise compréhension - alors soyez patient avec moi) J'avais une requête sur le théorème du PCP. Nous savons qu'après les trois premières étapes, à savoir. Réduction de degré, expansion et amplification de l'écart, nous avons un...
Il s'agit d'une continuation de ma question précédente sur les limites inférieures de communication pour les fonctions booléennes partielles . Quelqu'un peut-il suggérer une référence sur les limites inférieures pour la communication multipartite non déterministe? J'ai examiné les articles sur le...
Les jeux à deux provers et à un tour (2P1R) sont un outil essentiel pour la dureté de l'approximation. Plus précisément, la répétition parallèle de jeux à un tour à deux prouveurs permet d'augmenter la taille d'un écart dans la version de décision d'un problème d'approximation. Voir le sondage de...
Dans la complexité paramétrée, les gens utilisent la réduction à paramètres fixes (FPT) pour prouver la dureté W [t]. Théoriquement, une réduction FPT n'est pas une réduction du temps polynomial, car elle peut s'exécuter de façon exponentielle dans le paramètre k. Mais dans la pratique, toutes les...
Je lisais un article intitulé Random Oracles with (out) Programmability . Le dernier paragraphe de la section 2.3 se lit comme suit: [En utilisant notre nouvelle approche], il n'est pas nécessaire d'appliquer des techniques classiques de dérandomisation asymptotique (et uniforme) bien connues...
Étant donné que 2 problèmes NP-complets sont par définition réductibles l'un à l'autre, une solution à l'un d'eux peut donc être obtenue en utilisant une boîte noire résolvant l'autre, pourquoi n'ont-ils pas des ratios d'approximation similaires (en se référant à leurs homologues d'optimisation )?...
Cette question était motivée par une question posée sur stackoverflow . Supposons que l'on vous donne un arbre enraciné (c'est-à-dire qu'il y a une racine et que les nœuds ont des enfants, etc.) sur n nœuds (étiquetés 1 , 2 , … , n ).TTTnnn1,2,…,n1,2,…,n1, 2, \dots, n Chaque sommet a un poids...