Étant donné un graphe orienté, nous voulons décider s'il contient un cycle orienté de longueur paire. Ce document de 1997 de YUSTER et ZWICK déclare que le problème n'est pas connu pour être en ni pour complet.PPPNPNPNP Y a-t-il un résultat récent qui résout la complexité du problème de cycle pair...
Dans le chapitre 13 «Objets atomiques» du livre «Algorithmes distribués» de Nancy Lynch, la linéarisation (également connue sous le nom d'atomicité) s'est avérée être une propriété de sécurité. C'est-à-dire que sa propriété de trace correspondante est non vide, fermée par préfixe et fermée par...
Quelle est la définition standard de Planar 3-SAT? J'ai vu un certain nombre de définitions différentes. Quel est le document original qui l'a défini et a prouvé qu'il était
Y a-t-il des problèmes qui ne peuvent être résolus en temps polynomial que si P! = NP, et autrement résolu en (disons) temps?O(2n)O(2n)O(2^n) Un exemple simple serait: si P! = NP, calculez un test de primalité pour un nombre aléatoire de n bits, sinon, évaluez une position aléatoire dans le pire...
J'essaie de trouver une distribution sur vecteurs aléatoires, disons , sur la sphère de l'unité dimensionnelle (où ) qui minimise soumis à la contrainte \ mathbb {E} [x_i ^ Tx_j] = 0 .nnnx1,…,xnx1,…,xnx_1,\ldots, x_nkkkn>kn>kn > kmaxi≠jVar(xTixj)maxi≠jVar(xiTxj)\max_{i\neq j}...
Contexte: Le traitement des transactions est un sujet de recherche traditionnel en théorie des bases de données. De nos jours, les transactions distribuées sont popularisées par les systèmes de stockage distribué à grande échelle qui impliquent généralement la partition de données (également...
Dans l'article de 1965 « Sur la complexité de calcul des algorithmes » de Hartmanis et Stearns, les auteurs supposent que si une machine de Turing en temps réel calcule le nombre réel dans, par exemple, la base 10, alors est soit un nombre rationnel soit un numéro transcendantal.rrrrrr Existe-t-il...
La complexité de la preuve est l'un des domaines les plus élémentaires de la théorie de la complexité informatique. Un objectif ultime de ce domaine est de prouver , c'est-à-dire que tout prouveur ne peut pas fournir une preuve d'insatisfiabilité d'une formule d'entrée donnée. NP≠ c o...
C'est un fait assez bien connu que dériver une contradiction d'une inégalité (par exemple, ) dans la théorie de type Martin-Loef nécessite un univers.(0=1)→⊥(0=1)→⊥(0=1) \to \bot La preuve est également assez simple - en l'absence d'univers, nous pouvons effacer les dépendances de tout type...
Considérez le problème suivant: Étant donné une matrice nous voulons optimiser le nombre d'additions dans l'algorithme de multiplication pour calculer v ↦ M v .MMMv ↦ Mvv↦Mvv \mapsto Mv Je trouve ce problème intéressant en raison de ses liens avec la complexité de la multiplication matricielle (ce...
Les transducteurs considérés ici sont ceux que Wikipedia appelle les transducteurs à états finis . Le comportement d'un transducteur , qui est la relation qu'il calcule, est écrit : un mot est une sortie pour ssi .[ T ] y x x [ T ] yTTT[ T][T][T]yyyXxxx [ T] yx[T]yx[T]y Question: Le problème...
Où puis-je trouver une introduction aux automates probabilistes et ce qu'ils reconnaissent (certaines fonctions des mots à )? Existe-t-il un terme standard pour ces fonctions qui sont reconnues par les automates probabilistes, analogue aux «langages normaux» pour ce que les automates déterministes...
Soit HA L TnHALTnHALT_n la chaîne de longueur 2n2n2^n correspondant à la table de vérité du problème d'arrêt pour les entrées de longueur nnn . Si la séquence des complexités de Kolmogorov K( HA L Tn)K(HALTn)K(HALT_n) était O ( 1 )O(1)O(1) , alors l'une des chaînes de conseil serait utilisée...
Supposons que est un langage paramétré par rapport à un alphabet . La tranche de est , l'ensemble des instances de qui ont le paramètre . La classe de complexité contient les langages paramétrés tels que pour chaque , éventuellement avec un algorithme différent et un temps d'exécution polynomial...
Motivation : lors du développement d'outils de gestion des versions de données, nous avons fini par chercher des algorithmes pour «différencier» deux ensembles d'entiers, en proposant une séquence de transformations qui amènent un ensemble d'entiers à l'autre. Nous avons pu réduire ce problème au...
Le terme inversion de programme a plusieurs nuances de sens, mais a probablement commencé avec le travail de J. McCarthy de 1956, The Inversion of Functions Defined by Turing Machines dans le contexte de l'IA. À présent, de nombreuses connexions entre l'inversion de programme et d'autres domaines...
Je suis dans une situation où je dois montrer que la vérification de typage est décidable pour un calcul typé de manière dépendante sur lequel je travaille. Jusqu'à présent, j'ai pu prouver que le système est en train de normaliser fortement, et donc que l'égalité définitionnelle est décidable....
Je me demande si quelqu'un peut me donner l'intuition derrière pourquoi la positivité stricte des types de données inductifs garantit une forte normalisation. Pour être clair, je vois comment avoir des occurrences négatives conduit à la divergence, c'est-à-dire en définissant: data X where Intro :...
J'écris (lentement) une revue du Handbook of Chemoinformatics Algorithms pour SIGACT News. Un chapitre traite des implémentations logicielles actuelles, et les recherches dans la base de données (et d'autres applications) ne semblent pas tirer autant d'informations sur les graphiques que possible....
Supposons que l'on nous donne un graphe et les paramètres . Existe-t-il des plages de valeurs pour (ou est-ce faisable pour tous les ) pour lesquelles il est possible de tester si est loin d'avoir un ensemble indépendant de taille au moins dans le temps ?ggGk , ϵk,ϵk,\epsilonkkkkkkggGϵϵ\epsilonkkkO...