Nous savons que les solveurs SAT basés sur DPLL ne répondent pas correctement aux cas insatisfaisants de (principe du pigeon), par exemple sur "il y a une cartographie injective de n + 1 à n ":PHPPHP\mathrm{PHP}n+1n+1n+1nnn
Contexte Une formule à lecture unique sur un ensemble de portes (également appelée base) est une formule dans laquelle chaque variable d'entrée apparaît une fois. Les formules à lecture unique sont communément étudiées sur la base de De Morgan (qui a les portes 2 bits ET et OU, et la porte 1 bit...
Considérons une collection d'ensembles F = { F 1 , F 2 , … , F n } sur un ensemble de base U = { e 1 , e 2 , … , e n } où | F i | ≪ n et e i ∈ F i , et soit k un entier positif.F= { F1, F2, … , Fn}F=\{F_1,F_2,\dotsc,F_n\}U= { e1, e2, … , En}U=\{e_1,e_2,\dotsc,e_n\}| Fje||F_i| ≪\ll nneje∈ Fjee_i \in...
Le système de preuve probabiliste est communément appelé une restriction de , où Arthur ne peut utiliser que bits aléatoires et ne peut examiner que bits du certificat de preuve envoyé par Merlin (voir, http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).M A f ( n ) g ( n )PCP[ f( n ) , g(...
Je m'intéresse généralement à la méthode de forçage utilisée par Baker-Gill-Solovay et Cohen. Je recherche autant de sources que possible sur la technique elle-même ou son utilisation. Quelqu'un a-t-il des
Il est connu que minimiser la taille d'une expression régulière est PSPACE-complete même si nous avons un DFA comme spécification du langage . Quels sont les résultats si la langue est finie? On peut considérer ce problème dans deux modèles: L'entrée correspond à toutes les chaînes du langage, et...
J'espérais que quelqu'un pourrait m'expliquer pourquoi exactement le problème de produit de sous-ensemble est fortement NP-difficile alors que le problème de somme de sous-ensemble est faiblement NP-difficile. Somme Sous - ensemble: Étant donné X= { x1, . . . , xn}X={X1,...,Xn}X = \{x_1,...,x_n\}...
Il y a eu un travail fantastique sur le permanent en cours au cours des deux dernières décennies et je m'interroge depuis un moment sur la possibilité d'un algorithme Smooth P pour le permanent des matrices non négatives. Il y a bien sûr le fameux algorithme JSV mais c'est un fpras. En pensant à...
L'isomorphisme graphique ( ) est un bon candidat pour un problème intermédiaire . problèmes intermédiaires existent sauf si . Je recherche un problème naturel difficile pour sous réduction de Karp (Un problème graphique tel que ).GIGIGINPNPNPNPNPNPP=NPP=NPP=NPGIGIGIXXXGI<mpXGI<pmXGI...
Que se passe-t-il si nous définissons telle sorte qu'au lieu d'un circuit Turing-machine / polysize polytime, une machine Turing espace journal ou un circuit code le problème?P P A DPPAD{\bf PPAD} A C 0AC0{\bf AC^0} Donner récemment des algorithmes plus rapides pour la satisfiabilité des circuits...
FewP est la classe des problèmes avec polynôme lié au nombre de solutions (dans la taille d'entrée). On ne connaît pas problème -complete dans . Je voudrais savoir jusqu'où nous pouvons étendre cette observation.N P f e w PNPNPNPNPNPNPfewPFewPfewP Existe-t-il un problème naturel de complet avec une...
Dans nos travaux récents, nous résolvons un problème de calcul qui s'est posé dans un contexte combinatoire, en supposant que , où ⊕EXP≠⊕EXPEXP≠⊕EXP\mathsf{EXP} \ne \mathsf{\oplus{}EXP} est la version E X P de ⊕⊕EXP⊕EXP\mathsf{\oplus{}EXP}EXPEXP\mathsf{EXP} . Le seul papier sur...
Sous une forme simple: Un automate fini bidirectionnel peut-il reconnaître des graphes en vertex contenant un triangle avec des états ?vvvo ( v3)o(v3)o(v^3) Détails D' un intérêt ici sont graphiques de -vertex codées en utilisant une séquence de bords, chaque bord étant une paire de sommets...
Dans la complexité du circuit, nous avons des séparations entre les puissances des différents modèles de circuits. Dans la complexité de la preuve, nous avons des séparations entre les puissances des différents systèmes de preuve. Mais dans l'algorithmique, nous n'avons encore que peu de...
Quels sont quelques exemples majeurs de dérandomisation réussie ou du moins de progrès dans la démonstration de preuves concrètes vers l' objectif (pas la connexion de dureté aléatoire)?P= BPPP=BPPP=BPP Le seul exemple qui me vient à l'esprit est le test de primalité polynomiale déterministe AKS...
J'étudie un problème difficile pour la classe des formules booléennes quantifiées avec un nombre logarithmique d'alternances des quantificateurs. Un problème dans cette classe ressemblerait à: ∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F∀(x1,x2,…xa1)∃(xa1+1,…xa2),…∃(xalogn−1,…xalogn)F\forall...
Si vous êtes familier avec la vérification de programme, vous préférerez probablement lire la question avant le contexte . Si vous n'êtes pas familier avec la vérification de programme, vous pourrez peut-être encore répondre à cette question, mais vous préférerez probablement lire d'abord le...
Le théorème de Rice déclare que chaque propriété non triviale de l'ensemble reconnu par une machine de Turing est indécidable. Je recherche un théorème de type rizicole de complexité complexe qui nous dit quelles propriétés non triviales des ensembles NP sont
Deux documents que j'inclus sont: D. Kozen, "Indexation des classes subrécursives" , STOC, 1978. R. Ladner, «Sur la structure de la réductibilité du temps polynomial» , JACM, 1975.
Le problème #SAT est le problème canonique # P-complete. C'est un problème de fonction plutôt qu'un problème de décision. Il demande, étant donné une formule booléenne dans la logique propositionnelle, combien d'affectations satisfaisantes F a. Quelles sont les meilleures limites inférieures sur...