Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CNF:
Reports tagged with CNF:
TR02-069 | 14th November 2002
Luca Trevisan

#### A Note on Deterministic Approximate Counting for k-DNF

Revisions: 1

We describe a deterministic algorithm that, for constant k,
given a k-DNF or k-CNF formula f and a parameter e, runs in time
linear in the size of f and polynomial in 1/e and returns an
estimate of the fraction of satisfying assignments for f up to ... more >>>

TR07-054 | 25th May 2007
Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur

#### Testing Properties of Constraint-Graphs

We study a model of graph related formulae that we call
the \emph{Constraint-Graph model}. A
constraint-graph is a labeled multi-graph (a graph where loops
and parallel edges are allowed), where each edge $e$ is labeled
by a distinct Boolean variable and every vertex is
associate with a Boolean function over ... more >>>

TR15-100 | 16th June 2015
Bireswar Das, Patrick Scharpfenecker, Jacobo Toran

#### Succinct Encodings of Graph Isomorphism

It is well known that problems encoded with circuits or formulas generally gain an exponential complexity blow-up compared to their original complexity.

We introduce a new way for encoding graph problems, based on $\textrm{CNF}$ or $\textrm{DNF}$ formulas. We show that contrary to the other existing succinct models, there are ... more >>>

ISSN 1433-8092 | Imprint