Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Titus Dose:

TR19-050 | 20th March 2019
Titus Dose, Christian Glaßer

NP-Completeness, Proof Systems, and Disjoint NP-Pairs

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

TR18-055 | 26th March 2018
Titus Dose

Balance Problems for Integer Circuits

Revisions: 5

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

TR17-012 | 17th January 2017
Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

Emptiness Problems for Integer Circuits

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

TR16-031 | 7th March 2016
Titus Dose

Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

Revisions: 5

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

ISSN 1433-8092 | Imprint