0
$\begingroup$

Assuming $L \in NP$, meaning that L could be verified by some $V(x,y)$, such that there exists a polynomial $P(X)$ such that $|y| \leq P(|x|)$ for every $x \in L$.

I was wondering - can I assume something about the possible witness space? My intuition says that this number is bounded by $O(2^{P(|X|)})$ (all possible subsets of a certain problem, all possible strings by the length at most $P(X)$ etc...)

Thanks

$\endgroup$
2
$\begingroup$

The class of counting problems associated to languages in NP is called #P. More formally, $f:\mathbb{N}\rightarrow\mathbb{N}$ is in $\#P$ if there exists a nondeterministic polynomial time Turing machine $M$ such that for all $x\in\Sigma^*$, $f(x)$ is the number of accepting paths of $M$ on input $x$. This is equivalent to requiring the existence of a deterministic verifier $M(x,y)$ such that $f_M(x)=\big|\big\{y: M(x,y) \text{ accepts}\big\}\big|$.

You ask, given a language in $NP$ with it's verifier $M(x,y)$, can we approximate $f_M$? If the witnesses are of length $p(|x|)$ then obviously $0\le f_M(x)\le 2^{p(|x|)}$, but without knowing more about $M$ then we can't really say anything else about $f_M$. Note that computing $f_M$ is harder than asking whether a witness exists (obviously if you could count then you could determine existence). In fact, counting is considered much harder, as demonstrated by Toda's theorem (given an oracle for counting, one could decide the entire polynomial hierarchy in polynomial time).

So how hard is approximating such functions, or (allow me to focus on a specific $\#P$ complete language) how hard is it to approximate $\#SAT(\varphi)$, the number of satisfying assignments of a given CNF. In these lecture notes by Jonathan Katz, a constant factor approximation is considered, i.e. an algorithm producing a number inside the range $\left[2^{-k}\#SAT(\varphi),2^k\#SAT(\varphi)\right]$ for some fixed $k\in\mathbb{N}$. They show that with high probability, given an oracle for regular SAT, one can produce such an approximation in polynomial time (the algorithm can also be strengthen to yield an $1\pm p^{-1}(|\varphi|)$ approximation). So while exact counting is considered much harder than $NP$, an $NP$ oracle is enough to approximate $\#SAT$ with high probability.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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