Que sait-on de la complexité temporelle du problème suivant, que nous appelons 3-MUL? Étant donné un ensemble de entiers, y a-t-il des éléments tels que ?SSSnnna,b,c∈Sa,b,c∈Sa,b,c\in Sab=cab=cab=c Ce problème est similaire au problème 3-SUM, qui demande s'il y a trois éléments tels que (ou de...
L'état de nos connaissances sur les circuits arithmétiques généraux semble être similaire à l'état de nos connaissances sur les circuits booléens, c'est-à-dire que nous n'avons pas de bonnes limites inférieures. D'un autre côté, nous avons des limites inférieures de taille exponentielle pour les...
Il s'agit en quelque sorte d'une question ouverte - pour laquelle je m'excuse à l'avance. Y a-t-il des exemples de déclarations qui (apparemment) n'ont rien à voir avec la complexité ou les machines de Turing mais dont la réponse impliquerait ?P≠NPP≠NP\mathbf{P}\neq
J'envisage des classes de graphes qui peuvent être caractérisées par des sous-graphes interdits. Si une classe de graphes a un ensemble fini de sous-graphes interdits, il existe alors un algorithme de reconnaissance temporelle polynomiale trivial (on peut simplement utiliser la force brute). Mais...
Dans ce fil , la tentative de preuve Norbet Blum est succinctement réfutée en notant que la fonction Tardos est un contre-exemple du théorème 6.P≠NPP≠NPP \neq NP Théorème 6 : Soit une fonction booléenne monotone. Supposons qu'il existe un approximateur CNF-DNF A qui peut être utilisé pour prouver...
Cette question fait suite à la question sur les algorithmes d'ADN posée par Aadita Mehra . Dans ses commentaires, Joe Fitzsimmons a déclaré, en partie: [L] e rayon du système doit évoluer proportionnellement à la masse pour éviter cela. La puissance de calcul évolue au plus linéairement dans la...
Dans La complexité de calcul de l'optique linéaire ( ECCC TR10-170 ), Scott Aaronson et Alex Arkhipov soutiennent que si les ordinateurs quantiques peuvent être efficacement simulés par des ordinateurs classiques, la hiérarchie polynomiale s'effondre au troisième niveau. Le problème motivant est...
Afin de vérifier ma compréhension, je voudrais partager quelques réflexions sur les besoins énergétiques du calcul. Ceci fait suite à ma question précédente et pourrait être lié à la question de Vinay sur les lois de conservation . Il m'est apparu que, d'un point de vue thermodynamique, l'exécution...
Dans l'article "LA COMPLEXITÉ DES PROBLÈMES DE SATISFACABILITÉ" de Thomas J. Schaefer, l'auteur a mentionné que This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the...
Suite à une question précédente , quelles sont les meilleures limites inférieures de l' espace actuel pour SAT? Avec une borne inférieure d'espace, je veux dire ici le nombre de cellules de bande de travail utilisées par une machine Turing qui utilise un alphabet binaire de bande de travail. Un...
Je me demandais quels papiers je devrais lire pour comprendre cette question Une connexion inattendue à d'autres domaines des mathématiques tels que la géométrie algébrique ou la cohomologie supérieure. Peut-être même un domaine des mathématiques pas encore développé. Peut-être que quelqu'un...
Je recherche une référence pour le résultat suivant: Ajouter deux entiers dans la représentation factorisée est aussi difficile que factoriser deux entiers dans la représentation binaire habituelle. (Je suis presque sûr que c'est là-bas parce que c'est quelque chose que je me demandais à un moment...
Je lisais " Est-ce que P par rapport à NP est officiellement indépendant? ", Mais je suis resté perplexe. Il est largement admis dans la théorie de la complexité que . Ma question est de savoir si ce n'est pas prouvable (disons dans ). (Supposons que nous découvrions seulement que est indépendant...
Si un problème est NP-difficile (en utilisant des réductions de temps polynomiales), cela signifie-t-il qu'il est P-difficile (en utilisant l'espace logarithmique ou les réductions NC)? Il semble intuitif que s'il est aussi difficile que n'importe quel problème dans NP, il devrait être aussi...
Je sais que la complexité de la plupart des variétés de calculs lambda typés sans la primitive combinateur Y est bornée, c'est-à-dire que seules les fonctions de complexité bornée peuvent être exprimées, la borne devenant plus grande à mesure que l'expressivité du système de types croît. Je...
SSSI(n)={w∈S:|w|=n}I(n)={w∈S:|w|=n}I(n) = \{w \in S : |w| = n\}nnnT(w)T(w)T(w)AAAwwwAAAfn=maxw∈I(n)T(w).fn=maxw∈I(n)T(w). f_n = \max_{w \in I(n)} T(w). Définissons maintenant les ensembles de toutes les entrées avec la complexité de Kolmogorov , et définissons la séquence Ici est la séquence de...
Y a-t-il un exemple d'un problème naturel qui est dans BPP mais qui n'est pas connu pour être RP ou
Préambule Les systèmes de preuve interactifs et les protocoles Arthur-Merlin ont été introduits par Goldwasser, Micali et Rackoff et Babai en 1985. Au début, on pensait que le premier était plus puissant que le second, mais Goldwasser et Sipser ont montré qu'ils avaient le même pouvoir ( en ce qui...
Je suis curieux au sens large de ce que l'on sait des algorithmes de parallélisation en P. J'ai trouvé l'article wikipedia suivant sur le sujet: http://en.wikipedia.org/wiki/NC_%28complexity%29 L'article contient la phrase suivante: On ne sait pas si NC = P, mais la plupart des chercheurs...
De nombreux résultats importants dans la théorie de la complexité computationnelle, et en particulier la théorie de la complexité "structurelle", ont la propriété intéressante de pouvoir être compris comme suivant fondamentalement (comme je le vois ...) des résultats algorithmiques donnant un...