- Valid progams for NP imply every solution is a valid answer.
- NP not equals #P implies not all solutions are answers.
- Therefore, Validity implies NP=#P.
NP is the problem class for finding single verifiable solutions. #P is the related problem class of counting solutions.
If the proof is invalid, where is the flaw? By my reasoning, the proof is a three boolean variable three clause 2cnf expression, one of the smallest possible uniquely solvable boolean formulas, requiring three inferences to resolve.
My best counting benchmark (4cnf 4 coloring, degree 6 graph) took eleven weeks:
C4D6N66c.cnf + #P 472,406,068,323,174 retros 76865745357 infers 66385 billion
Send to pehoushek1 at gmail for single file C++ program, bob, for #sat, dimacs
forms. The three thousand line bob program can solve millions of small formulas
in a single run, but can be exponential on large formulas. bob also solves sat,
unsat, and qbfs, in roughly the same order of magnitude of time as #P, computing
nearly two trillion inferences per day. My main publication in the general area is Introduction to Qspace (Satisfiability 2002), containing a short proof of the theorem #P=#Q: the number of satisfying assignments to a boolean formula equals the number of valid quantifications of the formula. bob uses #P=#Q to solve qbfs, indicating coNP=NP=#P=#Q=PSpace=Exp. Garey and Johnson is the main reference.