En lisant l'article "Est-il temps de déclarer la victoire en comptant la complexité?" sur le blog "Godel's Lost Letter and P = NP" , ils ont mentionné la dichotomie pour les CSP. Après quelques liens après, googler et wikipeding, je suis tombé sur le théorème de Ladner : Théorème de Ladner: Si ,...
(Désolé si cela est bien connu.) Je voudrais donner un élément à l'un des agents, afin que l'agent obtienne l'élément avec la probabilité . Existe-t-il un outil cryptographique (ou autre) pour que chaque agent (et même chaque observateur) puisse être convaincu que le tirage au sort était...
Supposons que est un graphique avec un nombre à colorier d = χ ( G ) . Considérez le jeu suivant entre Alice et Bob. À chaque tour, Alice choisit un sommet et Bob répond avec une couleur en { 1 , … , d - 1 } pour ce sommet. Le jeu se termine lorsqu'un bord monochromatique est découvert. Soit X ( G...
Je voudrais poser une question sur un cas particulier de la question « Décider si un circuit NC 0 donné calcule une permutation » par QiCheng qui est resté sans réponse. Un circuit booléen est appelé circuit NC 0 k si chaque porte de sortie dépend syntaxiquement d'au plus k portes d'entrée. (Nous...
Dans la complexité de calcul, il existe une distinction importante entre les calculs monotones et généraux et un célèbre théorème de Razborov affirme que le 3-SAT et même MATCHING ne sont pas polynomiaux dans le modèle des circuits booléens monotones. Ma question est simple: existe-t-il un...
Edit: J'ai choisi la réponse avec le score le plus élevé avant le 06 décembre 2012. C'est une question douce. Le concept d'algorithmes (déterministes) remonte à la Colombie-Britannique. Qu'en est-il des algorithmes probabilistes? Dans cette entrée wiki , l'algorithme de Rabin pour le problème de...
L'étude de l'écologie et de l'évolution devient de plus en plus mathématique, mais la plupart des outils théoriques semblent provenir de la physique. Cependant, dans de nombreux cas, les problèmes ont un caractère très discret (voir par exemple SLBS00 ) et pourraient bénéficier d'une perspective...
Je lisais récemment Les deux dualités du calcul: types négatifs et fractionnaires . Le document développe les types de somme et les types de produits, donnant une sémantique aux types a - bet a/b. Contrairement à l'addition et à la multiplication, il n'y a pas un mais deux inverses...
Cette question a été migrée à partir de Computer Science Stack Exchange car il est possible d'y répondre sur Théoretics Computer Science Stack Exchange. Migré il y a 6 ans . Il semble que beaucoup de gens croient que , en partie parce qu'ils pensent que l'affacturage n'est pas résolu par le...
Étant donné une matrice binaire par (les entrées sont ou 1 ), le problème est de déterminer s'il existe deux vecteurs binaires v 1 ≠ v 2 tels que M v 1 = M v 2 (toutes les opérations effectuées sur Z ). Ce problème est-il difficile à NP?n M 0mmmnnnMMM000111v1≠v2v1≠v2v_1 \ne v_2Mv1=Mv2Mv1=Mv2Mv_1 =...
Y a-t-il un exemple de langue qui est en NPNPNP , mais où nous ne pouvons pas prouver ce fait directement en montrant qu'il existe un témoin polynomial d'appartenance à cette langue? Au lieu de cela, le fait que la langue est en NPNPNP serait prouvé en la réduisant à une autre langue en NPNPNP , où...
Grothendieck est décédé . Il a eu un impact massif sur les mathématiques du 20e siècle, se poursuivant jusqu'au 21e siècle. Cette question est posée quelque peu dans le style / l'esprit, par exemple, des contributions d' Alan Turing à l'informatique . Quelles sont les principales influences de...
Quels problèmes sont connus pour appartenir à mais ne sont pas connus pour appartenir à P ?BPPBPP\mathsf{BPP}PP\mathsf P Plus précisément, je m'intéresse aux problèmes indépendants , c'est-à-dire dont les dérandomisations ne sont pas connues pour être équivalentes. Par exemple, on sait que la...
Le problème des nnn -queens classiques demande, étant donné un entier positif nnn , s'il existe un tableau d'entiers satisfaisant aux conditions suivantes:Q[1..n]Q[1..n]Q[1..n] i1≤Q[i]≤n1≤Q[i]≤n1\le Q[i] \le n pour toutiii i ≠ jQ[i]≠Q[j]Q[i]≠Q[j]Q[i] \ne Q[j] pour touti≠ji≠ji\ne j...
Dans ma formation en informatique, je remarque de plus en plus que la plupart des problèmes discrets sont NP-complets (au moins), alors que l'optimisation de problèmes continus est presque toujours facilement réalisable, généralement grâce à des techniques de gradient. Y a-t-il des exceptions à...
J'ai trouvé ce document très intéressant. Pour résumer: il explique pourquoi, dans la pratique, vous trouvez rarement le pire cas d'un problème NP-complet. L'idée de l'article est que les instances sont généralement très sous ou très contraignantes, les deux étant relativement faciles à résoudre....
J'essaie de comprendre quelles sont les véritables différences entre le modèle d'acteur de la concurrence et le modèle de communication des processus séquentiels (CSP). Jusqu'à présent, le meilleur que j'ai pu trouver est que le modèle d'acteur permet au nombre et à la disposition des nœuds de...
Considérez le problème de couverture de l'ensemble minimal avec les restrictions suivantes: chaque ensemble contient au plus éléments et chaque élément de l'univers se produit dans au plus ensembles.kkkfff Exemple: le cas et est équivalent au problème de couverture minimale des sommets dans les...
Est-il possible de traduire une formule booléenne B en une conjonction équivalente de clauses Horn? L'article de Wikipédia sur HornSAT semble impliquer que c'est le cas, mais je n'ai pu chasser aucune référence. Notez que je ne veux pas dire "en temps polynomial", mais plutôt "du...
Je lis actuellement " Lambda-Calculus and Combinators " par Hindley et Seldin. Je ne suis pas un expert, mais je me suis toujours intéressé au calcul lambda en raison de son implication dans la programmation fonctionnelle (à commencer par Lisp et SICP, et maintenant avec R et Haskell). Dans "...