All reports by Author Titus Dose:

__
TR19-050
| 20th March 2019
__

Titus Dose, Christian Glaßer#### NP-Completeness, Proof Systems, and Disjoint NP-Pairs

__
TR18-055
| 26th March 2018
__

Titus Dose#### Balance Problems for Integer Circuits

Revisions: 5

__
TR17-012
| 17th January 2017
__

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau#### Emptiness Problems for Integer Circuits

__
TR16-031
| 7th March 2016
__

Titus Dose#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

Revisions: 5

Titus Dose, Christian Glaßer

The article investigates the relation between three well-known hypotheses.

1) Hunion: the union of disjoint complete sets for NP is complete for NP

2) Hopps: there exist optimal propositional proof systems

3) Hcpair: there exist complete disjoint NP-pairs

The following results are obtained:

a) The hypotheses are pairwise independent ...
more >>>

Titus Dose

We investigate the computational complexity of balance problems for $\{-,\cdot\}$-circuits

computing finite sets of natural numbers. These problems naturally build on problems for integer

expressions and integer circuits studied by Stockmeyer and Meyer (1973),

McKenzie and Wagner (2007),

and Glaßer et al (2010).

Our work shows that the ... more >>>

Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, ... more >>>

Titus Dose

We study the computational complexity of constraint satisfaction problems that are based on integer expressions and algebraic circuits. On input of a finite set of variables and a finite set of constraints the question is whether the variables can be mapped onto finite subsets of natural numbers (resp., finite intervals ... more >>>