P205: Enumeration of all models of $\phi$ by non-decreasing weight

P205: Enumeration of all models of $\phi$ by non-decreasing weight

Input:

A $\Gamma$-formula $\phi$.

Output:

All models of $\phi$ by non-decreasing weight.

Complexity:

If $\Gamma$ is Horn or width-2 affine, there exists a polynomial delay algorithm.

Comment:

Otherwise, such an algorithm does not exist unless $P = NP$.

Reference:

[Creignou2011] (Bibtex)