All reports by Author Heribert Vollmer:

__
TR12-079
| 14th June 2012
__

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer#### Verifying Proofs in Constant Depth

__
TR10-101
| 25th June 2010
__

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer#### Counting Classes and the Fine Structure between NC$^1$ and L.

__
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

__
TR07-045
| 24th April 2007
__

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

__
TR07-023
| 26th February 2007
__

Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor#### The Complexity of Problems for Quantified Constraints

__
TR06-153
| 19th October 2006
__

Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer#### The Complexity of Generalized Satisfiability for Linear Temporal Logic

Revisions: 1

__
TR05-024
| 8th February 2005
__

Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer#### Quantified Constraints: The Complexity of Decision and Counting for Bounded Alternation

__
TR04-100
| 23rd November 2004
__

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer#### The Complexity of Satisfiability Problems: Refining Schaefer's Theorem

Revisions: 1

__
TR03-018
| 28th March 2003
__

Matthias Galota, Heribert Vollmer#### Functions Computable in Polynomial Space

__
TR02-056
| 19th September 2002
__

Todd Ebert, Wolfgang Merkle, Heribert Vollmer#### On the Autoreducibility of Random Sequences

__
TR98-057
| 10th September 1998
__

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner#### Characterizing Small Depth and Small Space Classes by Operators of Higher Types

__
TR98-022
| 14th April 1998
__

Steffen Reith, Heribert Vollmer#### The Complexity of Computing Optimal Assignments of Generalized Propositional Formulae

__
TR96-035
| 27th March 1996
__

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner#### Probabilistic Type-2 Operators and ``Almost''-Classes

__
TR96-005
| 9th January 1996
__

Hans-Joerg Burtschick, Heribert Vollmer#### Lindstroem Quantifiers and Leaf Language Definability

Revisions: 1

Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Samir Datta, Meena Mahajan, Raghavendra Rao B V, Michael Thomas, Heribert Vollmer

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

Michael Bauland, Martin Mundhenk, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

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 >>>

Heribert Vollmer

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 >>>

Heribert Vollmer, Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor

In this paper we will look at restricted versions of the evaluation problem, the model checking problem, the equivalence problem, and the counting problem for quantified propositional formulas, both with and without bound on the number of quantifier alternations. The restrictions are such that we consider formulas in conjunctive normal-form ... more >>>

Michael Bauland, Thomas Schneider, Henning Schnoor, Ilka Schnoor, Heribert Vollmer

In a seminal paper from 1985, Sistla and Clarke showed

that satisfiability 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 ...
more >>>

Michael Bauland, Elmar Böhler, Nadia Creignou, Steffen Reith, Henning Schnoor, Heribert Vollmer

We consider constraint satisfaction problems parameterized by the set of allowed constraint predicates. We examine the complexity of quantified constraint satisfaction problems with a bounded number of quantifier alternations and the complexity of the associated counting problems. We obtain classification results that completely solve the Boolean case, and we show ... more >>>

Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer

Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer's dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are ... more >>>

Matthias Galota, Heribert Vollmer

We show that the class of integer-valued functions computable by

polynomial-space Turing machines is exactly the class of functions f

for which there is a nondeterministic polynomial-time Turing

machine with a certain order on its paths that on input x outputs a 3x3

matrix with entries from {-1,0,1} on each ...
more >>>

Todd Ebert, Wolfgang Merkle, Heribert Vollmer

A binary sequence A=A(0)A(1).... is called i.o. Turing-autoreducible if A is reducible to itself via an oracle Turing machine that never queries its oracle at the current input, outputs either A(x) or a don't-know symbol on any given input x, and outputs A(x) for infinitely many x. If in addition ... more >>>

Manindra Agrawal, Eric Allender, Samir Datta, Heribert Vollmer, Klaus W. Wagner

Motivated by the question of how to define an analog of interactive

proofs in the setting of logarithmic time- and space-bounded

computation, we study complexity classes defined in terms of

operators quantifying over oracles. We obtain new

characterizations of $\NCe$, $\L$, $\NL$, $\NP$, ...
more >>>

Steffen Reith, Heribert Vollmer

We consider the problems of finding the lexicographically

minimal (or maximal) satisfying assignment of propositional

formulae for different restricted formula classes. It turns

out that for each class from our framework, the above problem

is either polynomial time solvable or complete for ...
more >>>

Ronald V. Book, Heribert Vollmer, Klaus W. Wagner

We define and examine several probabilistic operators ranging over sets

(i.e., operators of type 2), among them the formerly studied

ALMOST-operator. We compare their power and prove that they all coincide

for a wide variety of classes. As a consequence, we characterize the

ALMOST-operator which ranges over infinite objects ...
more >>>

Hans-Joerg Burtschick, Heribert Vollmer

We show that examinations of the expressive power of logical formulae

enriched by Lindstroem quantifiers over ordered finite structures

have a well-studied complexity-theoretic counterpart: the leaf

language approach to define complexity classes. Model classes of

formulae with Lindstroem quantifiers are nothing else than leaf

language definable sets. Along the ...
more >>>