1. Valid progams for NP imply every solution is a valid answer.
  2. NP not equals #P implies not all solutions are answers.
  3. 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.


closed as not a real question by Tsuyoshi Ito, Lev Reyzin, Kaveh Jul 23 '12 at 18:19

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this and suggestions for sites that might welcome your question. Finally, if your question is closed for being out of scope, and you believe you can edit the question to make it a research-level question, please feel free to do so. Closing is not permanent and questions can be reopened, check the FAQ for more information. $\endgroup$ – Kaveh Jul 20 '12 at 6:47
  • 2
    $\begingroup$ Please also see the site policy on crank-friendly topics. Note that $\mathsf{PH} \subseteq \mathsf{P^{\#P}}$ so if what you say is true then $\mathsf{PH} \subseteq \mathsf{P^{NP}}$, i.e. $\mathsf{PH}$ collapses (which is a major open problem in complexity theory). $\endgroup$ – Kaveh Jul 20 '12 at 6:50

You have some fundamental misunderstanding of what a language $L$ being in $\mathsf{NP} \cap \mathsf{coNP}$ means. You'd need to show that there exist two machines: $M$ which is an $\mathsf{NP}$ machine, and $M'$, which is a $\mathsf{coNP}$ machine, such that $L$ is decided by $M$, and $L$ is also decided by $M'$. Each one should be able to solve the problem on its own, without being given the other one as an oracle, like you do.

Your construction on the other hand requires a linear number of calls to both $\mathsf{NP}$ and $\mathsf{coNP}$. In other words you have an alternating Turing machine with linear number of alternations. It's easy to see that such a machine can solve TQBF and therefore any problem in $\mathsf{PSPACE}$. Since the functional equivalent $\mathsf{FPSPACE}$ of $\mathsf{PSPACE}$ contains $\mathsf{\#P}$ and $\mathsf{FPSPACE}$ reduces easily (in the Turing reduction sense) to $\mathsf{PSPACE}$, your statement is not at all surprising. In fact your machine is more powerful than needed for solving $\mathsf{\#P}$ problems.

  • 5
    $\begingroup$ FPSPACE contains #P. Conflating decision and functional complexity classes is a type error which people frequently gloss over, but which is especially important to get right in your answer since the OP got it wrong (asking about #P being contained in NP and co-NP) in his question. $\endgroup$ – Huck Bennett Jul 19 '12 at 22:29
  • 1
    $\begingroup$ @Huck Thanks, fixed. In any case though, confusing functional and decision complexity classes is by far not the biggest problem with OP's reasoning. If it were, then there would be an easy fix :). $\endgroup$ – Sasho Nikolov Jul 20 '12 at 1:13
  • $\begingroup$ A "linear number of calls to both $NP$ and $coNP$" does not require that it's a $PSPACE$ machine. (Could mean that the simulation is only in $P^{NP}$, and $\# P$ is certainly not known to be in $P^{NP}$. Still, I can't follow much of what is said above.) $\endgroup$ – Ryan Williams Jul 20 '12 at 1:59
  • $\begingroup$ @Ryan Good point. On a first read I thought he may be using an alternating machine with linear number of alternations. On a second, maybe he's only claiming to make $O(n)$ calls to the NP machine... hard to tell what's going on! $\endgroup$ – Sasho Nikolov Jul 20 '12 at 6:23

After further review, if the given construction is valid, then Certificates for coNP are possible, so coNP is in NP, or else the relatively simple construction is invalid. Imagine, certificates for unsatisfiable problems!

The size increase would be O(M*N) on M k-clauses and N variables. The certificate can be obtained for an unsatisfiable formula by partitioning 2^N as #rootsat on the logical complement of the original unsatisfiable formula. I am not saying that the certificate is easy to construct, just that it Exists, for unsatisfiable formulas, among shallow binary trees where leafs are all labelled with #sat and #unsat. Language relativization does not actually seem to apply to the tree construction.

So, solving #P would still require binary search, which means O(N) calls to determine an N bit number. But the conclusion is entirely in NP, and so is easily checked once found! One certificate labels the precise number of solutions X in O(M) trees related to the original formula; and a second certificate labels 2^N - X as the number of solutions in O(M) trees related to the logical complement of the orignal formula.

The size of both certificates is O(M*N). Checking the certificates of the trees is easy, just adding of the #sat labels on each leaf of each tree. Every tree has #rootsat as the total number of satisfying assignments. So the conclusion now is that #P is entirely in NP, by using two easy to check certificates, one on the formula, and one on its complement.

coNP is also in NP, with an easily checkable certificate on the complementary formula. These certificates may be hard to construct, but they Exist. The construction deserves alot of attention to details, of course. If the construction is invalid, then please ignore my rambling.


Not the answer you're looking for? Browse other questions tagged or ask your own question.