Revoir ma preuve que co-np!= P

Question

c'est le travail de loisirs, pas mon travail. J'ai écrit cet extrait pour partager certaines idées sur CO-NP.

L'idée est de choisir une catégorie de problèmes dans la CO-NP, où la réponse correcte est difficile à vérifier en raison de la complexité du circuit, exprimez-la sous forme de formule SAT 1 in-K et de montrer qu'il existe également un bref certificat, dont La longueur des bits est exactement deux fois le nombre de clauses. Il pourrait être vrai ou faux que tous les problèmes de CO-NP ont un certificat aussi court dans cette forme (CO-NP?= NP), mais je montrent que, quel que soit celui-ci, le bref certificat de ce problème peut être fait arbitrairement difficile à trouver, à cause de la relation entrelacée avec le NP. Fondamentalement, je tiens à mettre en évidence une dépendance circulaire particulière entre les oracles de NP et CO-NP. L'argument à piétiner CO-NP= P est qu'aucun TM ne peut espérer attaquer le problème de la recherche du bref Certificat en temps subexponentiel, car la manière dont je définis le problème le permet de contenir une quantité arbitraire de "réelle aléatoire". Fondamentalement, il s'agit d'une recette spécifique pour créer un problème de co-np "monstre" à partir d'un simple certificat.

Maintenant, j'ai de nombreuses questions à quelqu'un avec une formation plus formelle que moi:

• Cette catégorie de problème a-t-elle été exprimée avec un nom différent?
• Est-ce une impasse évidente ou inexplorée?
• Comment puis-je exprimer les mêmes idées, mais plus formellement contre les capacités TM?

Answer 1

WTLU est à P.

algorithme:

• Faites la formule SAT 1 in-K en ajoutant une clause pour chaque paire de littéraux (x + ~ x)= 1 et en remplaçant ~ x avec une nouvelle variable.
• Choisissez un grand premier p, au moins plus grand que le nombre de clauses.
• Tournez la formule SAT 1 in-K dans un système d'équations linéaires MODULO P.Chaque clause d'origine sous la forme (x, y, z ...)= 1 devient une équation (x, y, z ...)= 1 mod p.
• Effectuez une élimination gaussienne.
• Si la formule était une instance WTLU, une contradiction est trouvée avant que la forme de ligne Echelon n'est atteinte, sous la forme d'une équation contradictoire 0= k mod P (avec k!= 0).

pourquoi ça marche:

S'il y a deux ensembles de clauses couvrant le même ensemble de littéraux, tels que (C1 + C2 + C3 ...)= X et (C1 '+ C2' + C3 '...)= Y et X!= Y, alors c'est aussi le cas modulo p.Ainsi, le système d'équations modulo p n'est pas satisfait non plus non plus.

Answer 2

Voici un contre-argument. Une structure de preuve similaire pourrait être facilement utilisée pour prouver que XOR-SAT est difficile.

1. Prenez une formule XOR-SAT insatisfaite avec un grand espace. Vous ne pouvez pas le résoudre avec un algorithme ressemblant à une résolution.

2. Il existe maintenant un bref certificat insatisfaisable, car Xor-Sat est dans P.

3. Si vous ne connaissez pas l'élimination, vous combinez des clauses aléatoires ensemble jusqu'à ce que deux clauses aient les mêmes variables, une rangée est égale à zéro et l'autre rangée équivaut à une. Doubler est un cas particulier d'ajout où les clauses n'ont pas de littéraux en commun.

4. Ajoutez des clauses et des variables aléatoires à la formule XOR-SAT pour rendre plus difficile la tâche de faire au hasard.

Mais en réalité, vous pouvez faire une élimination gaussienne dans une quantité polynomiale de temps et d'espace jusqu'à ce que deux rangées s'annulent à produire 0= 1.

Pour développer votre argument et le rendre intéressant, vous auriez besoin de montrer au moins qu'il existe une différence fondamentale avec XOR-SAT, car il n'y a pas de processus similaire à l'élimination où vous pouvez sortir les variables une par une pendant le processus d'isolement des 2 ensembles de clauses conflictuels tout en ignorant les informations supplémentaires.