Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Post's lattice:
TR07-045 | 24th April 2007
Heribert Vollmer

The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

We study the complexity of the following algorithmic problem: Given a Boolean function $f$ and a finite set of Boolean functions $B$, decide if there is a circuit with basis $B$ that computes $f$. We show that if both $f$ and all functions in $B$ are given by their truth-table, ... more >>>

TR08-028 | 5th December 2007
Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments

In a seminal paper from 1985, Sistla and Clarke showed
that the model-checking problem for Linear Temporal Logic (LTL) is either NP-complete
or PSPACE-complete, depending on the set of temporal operators used.
If, in contrast, the set of propositional operators is restricted, the complexity may decrease.
... more >>>

ISSN 1433-8092 | Imprint