J'ai posé cette question il y a 10 jours sur cs.stackexchange ici mais je n'ai pas eu de réponse. Dans un article très célèbre (dans la communauté des réseaux), Wang et Crowcroft présentent des résultats de complétion du calcul de chemin sous plusieurs contraintes additives / multiplicatives. Le...
Comme tout le monde le sait, le célèbre livre de Garey et Johnson (et bien d'autres) fournit une excellente référence pour la technique de réduction en milieu classique. Existe-t-il des enquêtes ou des livres sur le thème de la technique de réduction dans l'algorithme paramétré, disons la réduction...
Existe-t-il un moyen de coder une instance de sous-ensemble de somme ou le problème de partition numérique afin qu'une (petite) solution à une relation entière donne une réponse? Si ce n'est pas définitivement, dans un sens probabiliste? Je sais que LLL (et peut-être PSLQ) ont été utilisés avec un...
Comme tout le monde le sait, le SAT est complet pour les réductions de plusieurs P de rapport au temps polynomial. Elle est toujours complète par rapport aux réductions multiples de A C 0 .N PNP\mathsf{NP}A C0UNEC0\mathsf{AC^0} Ma question est quelle est la profondeur minimale requise pour les...
Problème: étant donné représenté par un circuit booléen, générer un uniformément aléatoire tel que (ou sortie si un tel n'existe pas). ϕ : { 0 , 1 }n→ { 0 , 1 }ϕ:{0,1}n→{0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }nX∈{0,1}nx \in \{0,1\}^nϕ ( x ) = 1ϕ(X)=1\phi(x)=1⊥⊥\perpXXx Clairement, ce...
Il me semble que la plupart des théoriciens de la complexité croient généralement à la règle philosophique suivante: Si nous ne pouvons pas trouver un algorithme efficace pour le problème , et nous pouvons réduire problème A à un problème B , alors il n'y a probablement pas un algorithme efficace...
La complexité classe PPAD a été inventé par Christos Papadimitriou dans son 1994 fondateur du papier . La classe est conçue pour capturer la complexité des problèmes de recherche où l'existence d'une solution est garantie par "Argument de parité dans les graphes dirigés": s'il y a un sommet...
La semaine dernière, je lisais à nouveau le transcript de Leslie's Lamport en 1982 d'une conférence qu'il a donnée sur les problèmes résolus, les problèmes non résolus et les non-problèmes dans la concurrence . Le document est facilement lisible, mais l'une des choses qui m'a fait réfléchir est...
Lance Fortnow a récemment affirmé que prouver L! = NP devrait être plus facile que prouver P! = NP : NP séparé de l'espace logarithmique. J'ai donné quatre approches dans une enquête pré-blog 2001 sur la diagonalisation (section 3), mais aucune n'a échoué. Cela devrait être beaucoup plus facile que...
Il y a quelque temps, j'ai publié une demande de référence pour les problèmes de graphe où nous voulons trouver une partition à 2 des bords où les deux ensembles remplissent une propriété sans rapport avec leur cardinalité. J'essayais de prouver que le problème suivant est NP-difficile: Étant donné...
Les éléments suivants peuvent-ils tous tenir simultanément? LsLsL_s est contenu dansLs+1Ls+1L_{s+1} pour tous les entiers positifssss . { 0 , 1 }L=⋃sLsL=⋃sLsL = \bigcup_s L_s est la langue de tous les mots finis sur .{0,1}{0,1}\{0,1\} Il y a une classe de complexité et une notion de réduction...
Lorsque nous voulons prouver qu'un est N P- complet, alors l'approche standard est de montrer à L une réduction de plusieurs un calculable en temps polynomial d'un problème N P- complet connu . Dans ce contexte, nous n'avons pas besoin d'une limite stricte sur la durée de la réduction. Il suffit...
'Étant donné a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , y a-t-il x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by=cax2+by=cax^2+by=c ' est NPNP\mathsf{NP} -complet. À quelle classe de complexité «Étant donné a,b,c∈Na,b,c∈Na,b,c\in\Bbb N , y a-t-il x,y∈Nx,y∈Nx,y\in\Bbb N , ax2+by2=cax2+by2=cax^2+by^2=c...
Cet article prouve que dans un jeu avec des portes et des plaques de pression, il est difficile pour PSPACE de déterminer si l'avatar (du joueur) peut atteindre un emplacement donné. Cela est prouvé par une réduction de TQBF , et la longueur des solutions résultantes dépend exponentiellement du...
Le SAT unique est le problème bien connu: étant donné une formule CNF , est-il vrai que F a exactement un modèle?FFFFFF Je m'intéresse au problème «Exactement -SAT»: étant donné une formule CNF F et un entier m > 1 , est-il vrai que F a exactement m modèles?mmmFFFm>1m>1m>1FFFmmm Les deux...
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...
Cette question n'est peut-être pas technique. En tant que locuteur non natif et TA pour la classe d'algorithmes, je me suis toujours demandé ce que signifie gadget dans «gadget de clause» ou «gadget variable». Le dictionnaire dit qu'un gadget est une machine ou un appareil, mais je ne sais pas...
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...
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...
Y a-t-il unL∈NPL∈NPL\in {\bf NP} avec les propriétés suivantes: On sait que implique P = N P .L∈PL∈PL\in {\bf P}P=NPP=NP{\bf P}={\bf NP} Il n'y a pas (connu) polynomiale réduction de Turing (ou un autre N P problème -complete) à L .SATSATSATNPNP{\bf NP}LLL En d'autres termes, si un algorithme...