<p>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. </p>

<p>Your construction on the other hand requires a linear number of calls to <em>both</em> $\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.</p>

CC BY-SA 3.0
2012-07-19T22:29:09.947Z
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.
Huck Bennett
CC BY-SA 3.0
2012-07-20T01:13:05.857Z
@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 :).
Sasho Nikolov
CC BY-SA 3.0
2012-07-20T01:59:43.813Z
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.)
Ryan Williams
CC BY-SA 3.0
2012-07-20T06:23:13.633Z
@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!
Sasho Nikolov
CC BY-SA 3.0
2012-07-19T17:26:01.600Z
2012-07-20T01:37:09.883Z
2012-07-20T01:37:09.883Z
Sasho Nikolov
<p>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!  </p>

<p>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.   </p>

<p>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.  </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-07-20T15:23:55.690Z
2012-07-20T15:23:55.690Z
daniel pehoushek
<ol>
<li>Valid progams for NP  imply    every solution is a valid answer.  </li>
<li>NP not equals #P      implies  not all solutions are answers.  </li>
<li>Therefore, Validity   implies  NP=#P. </li>
</ol>

<p>NP is the problem class for finding single verifiable solutions.
#P is the related problem class of counting solutions.</p>

<p>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.</p>

<p>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,<br>
unsat, and qbfs, in roughly the same order of magnitude of time as #P, computing<br>
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.  </p>

CC BY-SA 3.0
2012-07-20T06:47:17.497Z
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.
Kaveh
CC BY-SA 3.0
2012-07-20T06:50:08.383Z
Please also see [the site policy on crank-friendly topics](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics/281#281). 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).
Kaveh
<cc.complexity-theory><complexity-classes><computability><counting-complexity>
Validity implies NP=#P?
daniel pehoushek
# Validity implies NP=#P?

(Asked by: username_0 on 2012-07-19)

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.

**Tags:** cc.complexity-theory, complexity-classes, computability, counting-complexity

> **Comments:**
> **username_1**: 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.  
> **username_1**: Please also see [the site policy on crank-friendly topics](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics/281#281). 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).  

---

## 2 answers

### Answer by username_2 on 2012-07-19. Score: 12

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.

> **Comments:**
> **username_3**: 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.  
> **username_2**: @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 :).  
> **username_4**: 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.)  
> **username_2**: @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!  

---

### Answer by username_0 on 2012-07-20. Score: -5

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.


---

