In 2002, I published a theorem, #P=#Q, that says the number of satisfying assignments equals the number of valid quantifications for any boolean formula. I have done alot of followup work, and am interested in discussion. Fairly recently, I discovered a proof that coNP=NP=#P.
I have other results too, that would benefit from discussion.
Daniel Pehoushek
The Proof of coNP = NP = #P
A global notion of validity is introduced. Essentially, the declaration is that
any one of all possible solutions can be used to return an answer by the coNP
(resp. NP) program. If some solutions are unusable, the program is invalid,
because it could then return wrong answers with small effort. With global
validity, equality is nearly definitional among the three classes. The dimacs
proof is just for fun, showing the proof is easy and uncircular.
coNP: Are there zero solutions?
NP: Is there at least one polynomially verifiable solution?
#P: The problem of counting all solutions.
When zero solutions exist, coNP = NP = #P.
Let j solutions exist, 0 < j < 2^N + 1, without loss of generality.
A0 Valid coNP program == Any of j satisfiable solutions can be returned as an answer.
A1 Assume a valid coNP program.
A2 Assume coNP is unequal to #P :
A3 Some solution cannnot be found by the valid coNP program.
A4 Less than j satisfiable solutions can be returned as an answer.
A5 coNP unequal to #P results in an invalid coNP program.
A6 So, valid coNP programs imply coNP equals #P.
B0 Valid NP program == Any of j satisfiable solutions can be returned as an answer.
B1 Assume a valid NP program.
B2 Assume NP is unequal to #P:
B3 Some solution cannot be found by the valid NP program.
B4 Less than j satisfiable solutions can be returned as an answer.
B5 NP unequal to #P results in an invalid NP program.
B6 So, valid NP programs imply NP equals #P.
Conclusion: coNP = NP = #P.
c The reasoning of proofs A && B is definitional, not circular.
c A dimacs formula is presented; Bob counts 1 solution with 12 inferences.
c 1 = Valid coNP program
c 2 = Valid NP program
c 3 = coNP equals #P
c 4 = NP equals #P
c 5 = coNP equals NP
c 6 = Less than j satifiable solutions can be returned as an answer (coNP).
c 7 = Less than j satifiable solutions can be returned as an answer (NP).
c 8 = Any of j satisfiable solutions can be returned as an answer (coNP).
c 9 = Any of j satisfiable solutions can be returned as an answer (NP).
c
c (1 implies 8)
c (~3 implies 6)
c (6 implies ~8)
c (2 implies 9)
c (~4 implies 7)
c (7 implies ~9)
c ((3 && 4) imply 5)
c (~1 implies false)
c (~2 implies false)
cs 1 2 3 4 5 ~6 ~7 8 9
c
p cnf 9 9
~1 8
3 6
~6 ~8
~2 9
4 7
~7 ~9
~3 ~4 5
1
2
s 1 2 3 4 5 ~6 ~7 8 9
Comments
Post a Comment