Une question récente (voir les conséquences de NP = PSPACE ) a demandé des conséquences "désagréables" de . Les réponses liste assez peu de conséquences de l' effondrement, y compris N P = c o N P et d' autres, en fournissant beaucoup de raisons de croire N P ≠ P S P A C E...
Il est bien établi que , pour chaque matroïde MMM et toute fonction de pondération www , il sort un algorithme GreedyBasis (M, w )GreedyBasis(M,w)\mbox{GreedyBasis}(M,w) qui renvoie une base pondérale maximale de MMM . Alors, la direction inverse est-elle également vraie? Autrement dit, s'il existe...
Soit la fonction majoritaire, c'est-à-dire f ( x ) = 1 si et seulement si ∑ n i = 1 x i > n / 2 . Je me demandais s'il y avait une preuve simple du fait suivant (par «simple», je veux dire ne pas compter sur la méthode probabiliste comme Valiant 84 ou sur les réseaux de tri; fournissant de...
J'étudie récemment le modèle de calcul BSS (cf. par exemple Complexité et calcul réel; Blum, Cucker, Shub, Smale.) Pour les réels , on montre que, étant donné un système de polynômes f 1 , ⋯ , f m ∈ R [ x 1 , ⋯ , x n ] , l'existence de zéros est N P R -complète. Cependant, je me demande si ces f...
La manière habituelle de prouver l'indécidabilité est la réduction d'un problème RE-complet tel que le problème d'arrêt, la validité dans la logique du premier ordre, la satisfiabilité des équations diophantiennes, etc. Il est connu qu'il y a des problèmes récursivement énumérables, mais...
Le titre est un peu trompeur: mais j'espère que la question n'est pas: Grønlund et nouveau résultat Pettie montrant que 3sum a seulement la complexité de l' arbre de décision m'a demander:O ( n3 / 2)O(n3/2)O(n^{3/2}) Y a-t-il un exemple simple d'un problème avec une complexité d'arbre de décision...
En lisant les questions exemples où l'unicité de la solution permet de trouver plus facilement , une nouvelle (? Plus facile) question est venue à l' esprit: en fait , nous ne savons pas si le graphique Isomorphisme ( problème) est dans P .G IgjeGIPPP Mais que se passe-t-il si nous supposons que et...
Quelles sont les carrières typiques des informaticiens théoriques (personnes titulaires d'un diplôme d'études supérieures en informatique théorique)? Quels types d'industries et d'institutions recherchent des connaissances théoriques en informatique? Quelles carrières les informaticiens théoriques...
Il est bien connu que la complexité de distinguer une pièce biaisée une pièce équitable est θ ( ϵ - 2 ) . Y a-t-il des résultats pour distinguer une pièce p d' une pièce p + ϵ ? Je peux voir que pour le cas particulier de p = 0 , la complexité sera ϵ - 1 . J'ai le pressentiment que la complexité...
J'ai une réduction du problème de partition suivant à un certain problème de planification: Entrée: Une liste une1⩽ ⋯ ⩽ anune1⩽⋯⩽unena_1\leqslant\cdots\leqslant a_n d'entiers positifs dans l'ordre non décroissant. Question: Existe-t-il un vecteur ( x1, … , Xn) ∈ { - 1 , 1...
Contexte: La complexité de l'arbre de décision ou la complexité des requêtes est un modèle de calcul simple défini comme suit. Soit F: { 0 , 1 }n→ { 0 , 1 }F:{0,1}n→{0,1}f:\{0,1\}^n\to \{0,1\} une fonction booléenne. La complexité de requête déterministe de FFf , notée D ( f)ré(F)D(f) , est le...
Étant donné un algorithme fonctionnant au temps , nous pouvons le convertir en une famille de circuits uniformes "triviaux" pour le même problème de taille au plus ≈ t ( n ) log t ( n ) .t(n)t(n)t(n)≈t(n)logt(n)≈t(n)logt(n)\approx t(n)\log t(n) D'un autre côté, il se pourrait que nous ayons des...
Dans le problème d'extensibilité, on nous donne une partie de la solution et nous voulons décider si nous pouvons l'étendre à une solution complète. Certains problèmes d'extensibilité peuvent être résolus efficacement tandis que d'autres problèmes d'extensibilité transforment un problème facile en...
Connaissez-vous des problèmes (de préférence au moins assez bien connus) où, pour une taille de problème pratique , un algorithme exponentiel s'exécute beaucoup plus rapidement qu'un homologue polynomial le plus connu. Par exemple, supposons qu'un problème ait une taille pratique * de et qu'il...
La hiérarchie est une hiérarchie de classes de complexité en complexité paramétrée, voir le Complexity Zoo pour les définitions. Une définition alternative définit utilisant la définissabilité pondérée de Fagin pour les logique du premier ordre, voir le manuel de Flum et Grohe...
Étant donné un groupe de permutations sur [ n ] = { 1 , ⋯ , n } , et deux vecteurs u , v ∈ Γ n où Γ est un alphabet fini qui n'est pas tout à fait pertinent ici, la question est de savoir s'il existe des π ∈ G tel que π ( u ) = v où π ( u ) signifie appliquer la permutation π sur u de manière...
Je lis le document "Fast Paxos" de Leslie Lamport et je suis coincé avec les preuves d'exactitude des deux Paxos classiques et Fast Paxos. Par souci de cohérence, la valeur vvv choisie par le coordinateur dans la phase 2a2a2a du tour iii doit satisfaire CP(v,i):CP(v,i):CP(v,i): Pour tout...
En écrivant un petit post sur la complexité des jeux vidéo Nibbler et Snake ; J'ai trouvé que les deux peuvent être modélisés comme des problèmes de reconfiguration sur les graphes planaires; et il semble peu probable que de tels problèmes n'aient pas été bien étudiés dans le domaine de la...
Étant donné que je suis intéressé par les analyseurs (principalement les grammaires d'expression des analyseurs), je me demande s'il y a du travail qui donne un traitement catégorique de l'analyse. Toute référence sur les applications de la théorie des catégories à l'analyse syntaxique est très...
J'ai lu un peu sur la méthode de la somme des carrés (SOS) de l' enquête de Barak & Steurer et les notes de cours de Barak . Dans les deux cas, ils balaient les problèmes de précision numérique sous le tapis. D'après ma compréhension (certes limitée) de la méthode, ce qui suit devrait être...