Skip to main content
20 votes
Accepted

Counting the number of satisfying assignments in a POSITIVE CNF-SAT

This is still #P-complete [1]. This problem is usually referred to as montone (#)SAT. Monotone #2-SAT is already #P-complete (this is equivalent to counting vertex covers of a graph). [1] Roth, Dan. "...
holf's user avatar
  • 2,174
15 votes

Counting the number of satisfying assignments in a POSITIVE CNF-SAT

This problem is Monotone-SAT. It is #P-Complete under Cook Reductions. It is one of those problems that are "easy to decide but hard to count." I recommend the following paper. Self-Reducibility of ...
Tayfun Pay's user avatar
  • 2,618
11 votes
Accepted

Sampling monotone Boolean functions

In [1], the paper where Propp & Wilson introduce the "coupling from the past" technique for MCMC sampling, they also outline a "heat bath algorithm" applicable to a certain kind of spin system ...
mhum's user avatar
  • 3,392
7 votes
Accepted

3-SAT mixed with 2-SAT formulas

If $F_3$ and $F_2$ are both monotone, satisfiability can be checked in polynomial time (or even in coNLOGTIME), as $F_3\land F_2$, which is also monotone, is satisfiable iff it is satisfied by the $\...
Emil Jeřábek's user avatar
6 votes

Is a monotone boolean function monotone as a multilinear polynomial?

Yes. Let $f : \{-1,1\}^n \to \mathbb{R}$, and let $F : [-1,1]^n \to \mathbb{R}$ be its multilinear extension. If $f$ is monotone, then so is $F$. proof: Fix a variable index $i$; we'll show that $\...
Andrew Morgan's user avatar
5 votes
Accepted

Reductions and projections in circuit complexity

The definition in [Arora, Barak] is the usual definition in algebraic complexity (dating back to the work of Valiant). But in descriptive complexity theory (e.g. N. Immerman, Descriptive Complexity, ...
Eric Allender's user avatar
4 votes
Accepted

Lower bound for constant degree monotone arithmetic circuits

The Nisan--Wigderson polynomials are one example. That is, let $$ \mathrm{NW}_{n,m,d}(\vec{x}) := \sum_{\substack{p(t) \in \mathbb{F}_m[t] \\ \deg(p) \le d}} x_{1,p(1)} \cdots x_{n,p(n)}. $$ Let $k$ ...
Robert Andrews's user avatar
2 votes

Treewidth of monotone graph classes with bounded cliquewidth

Yes, the statement is true. Take a monotone class with bounded cliquewidth. We show that the size of bicliques is bounded. If it were not bounded, we could remove some edges and vertices (by ...
Jan's user avatar
  • 61

Only top scored, non community-wiki answers of a minimum length are eligible