Problem Detail: Wiki (http://en.wikipedia.org/wiki/Sharp-P) says ‘In computational complexity theory, the complexity class #P (pronounced “number P” or, sometimes “sharp P” or “hash P”) is the set of the counting problems associated with the decision problems in the set NP’. Is there a counting version for CoNP problems?
Asked By : Turbo
Answered By : Yuval Filmus
Expanding on Timot’s comment, $# P$ consists of all functions which can be expressed as the number of accepting computations of some non-deterministic Turing machine running in polynomial time. It is also the class of all functions which can be expressed at the number of non-accepting computations of some non-deterministic Turing machine running in polynomial time (exercise). If $f in # P$ then ${ x : f(x) geq 1 } in N! P$ and ${x : f(x) = 0 } in mathrm{co}N! P$; and vice versa, if $L in N!P$ ($L in mathrm{co}N!P$) then it can be expressed in the form ${ x : f(x) geq 1 }$ (${ x : f(x) = 0 }$) for some $f in # P$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14649 Ask a Question Download Related Notes/Documents
