Martin Loebbing, Ingo Wegener

An increasing number of results in graph theory, combinatorics and

theoretical computer science is obtained with the help of computers,

e.g. the proof of the Four Colours Theorem or the computation of

certain Ramsey numbers. Binary decision diagrams, known as tools in

hardware verification ...
more >>>

Bernd Borchert, Frank Stephan

Rice's Theorem says that every nontrivial semantic property

of programs is undecidable. It this spirit we show the following:

Every nontrivial absolute (gap, relative) counting property of circuits

is UP-hard with respect to polynomial-time Turing reductions.

Andrei A. Bulatov

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite

relational structure H can be expressed as follows: given a

relational structure G over the same vocabulary,

determine the number of homomorphisms from G to H.

In this paper we characterize relational structures H for which

#CSP(H) can be solved in ...
more >>>

Holger Dell, Thore Husfeldt, Martin WahlĂ©n

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting ... more >>>

Oded Goldreich

We consider the complexity of enumerating ordered sets, defined as solving the following type of a computational problem: For a predetermined ordered set, given $i\in\N$, one is required to answer with the $i^{th}$ member of the set (according to the predetermined order).

Our focus is on countable sets such as ... more >>>