All reports by Author Christian Glaßer:

__
TR19-050
| 20th March 2019
__

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

__
TR17-012
| 17th January 2017
__

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

__
TR13-188
| 13th December 2013
__

Christian Glaßer, Maximilian Witek#### Autoreducibility and Mitoticity of Logspace-Complete Sets for NP and Other Classes

__
TR13-047
| 27th March 2013
__

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek#### Autoreducibility of Complete Sets for Log-Space and Polynomial-Time Reductions

Comments: 1

__
TR11-053
| 11th April 2011
__

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek#### The Complexity of Solving Multiobjective Optimization Problems and its Relation to Multivalued Functions

__
TR10-031
| 4th March 2010
__

Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek#### Hardness and Approximability in Multi-Objective Optimization

__
TR09-076
| 19th August 2009
__

Christian Glaßer, Christian Reitwießner, Maximilian Witek#### Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman

Revisions: 1

__
TR08-029
| 7th January 2008
__

Christian Glaßer, Christian Reitwießner, Victor Selivanov#### The Shrinking Property for NP and coNP

__
TR07-094
| 3rd August 2007
__

Christian Glaßer, Heinz Schmitz, Victor Selivanov#### Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

__
TR07-018
| 1st March 2007
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### The Informational Content of Canonical Disjoint NP-Pairs

__
TR06-090
| 22nd June 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang#### Non-Mitotic Sets

__
TR06-069
| 11th May 2006
__

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner#### The Complexity of Unions of Disjoint Sets

__
TR05-147
| 5th December 2005
__

Christian Glaßer, Stephen Travers#### Machines that can Output Empty Words

__
TR05-072
| 11th July 2005
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### Survey of Disjoint NP-Pairs and Relations to Propositional Proof Systems

__
TR05-068
| 7th July 2005
__

Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang#### Redundancy in Complete Sets

__
TR05-035
| 24th March 2005
__

Christian Glaßer, Stephen Travers, Klaus W. Wagner#### A Reducibility that Corresponds to Unbalanced Leaf-Language Classes

__
TR05-011
| 21st December 2004
__

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang#### Autoreducibility, Mitoticity, and Immunity

__
TR04-106
| 19th November 2004
__

Christian Glaßer, Alan L. Selman, Liyu Zhang#### Canonical Disjoint NP-Pairs of Propositional Proof Systems

__
TR04-037
| 14th April 2004
__

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner#### Generation Problems

__
TR04-019
| 15th January 2004
__

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta#### Properties of NP-Complete Sets

__
TR04-011
| 16th January 2004
__

Christian Glaßer#### Counting with Counterfree Automata

__
TR03-069
| 13th August 2003
__

Elmar Böhler, Christian Glaßer, Daniel Meister#### Small Bounded-Error Computations and Completeness

__
TR03-027
| 21st April 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta#### Reductions between Disjoint NP-Pairs

__
TR03-011
| 17th February 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang#### Disjoint NP-Pairs

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

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

Christian Glaßer, Maximilian Witek

We study the autoreducibility and mitoticity of complete sets for NP and other complexity classes, where the main focus is on logspace reducibilities. In particular, we obtain:

- For NP and all other classes of the PH: each logspace many-one-complete set is logspace Turing-autoreducible.

- For P, the delta-levels of ...
more >>>

Christian Glaßer, Dung Nguyen, Christian Reitwießner, Alan Selman, Maximilian Witek

We investigate the autoreducibility and mitoticity of complete sets for several classes with respect to different polynomial-time and logarithmic-space reducibility notions.

Previous work in this area focused on polynomial-time reducibility notions. Here we obtain new mitoticity and autoreducibility results for the classes EXP and NEXP with respect to some restricted ... more >>>

Krzysztof Fleszar, Christian Glaßer, Fabian Lipp, Christian Reitwießner, Maximilian Witek

Instances of optimization problems with multiple objectives can have several optimal solutions whose cost vectors are incomparable. This ambiguity leads to several reasonable notions for solving multiobjective problems. Each such notion defines a class of multivalued functions. We systematically investigate the computational complexity of these classes.

Some solution notions S ... more >>>

Christian Glaßer, Christian Reitwießner, Heinz Schmitz, Maximilian Witek

We systematically study the hardness and the approximability of combinatorial multi-objective NP optimization problems (multi-objective problems, for short).

We define solution notions that precisely capture the typical algorithmic tasks in multi-objective optimization. These notions inherit polynomial-time Turing reducibility from multivalued functions, which allows us to compare the solution notions and ... more >>>

Christian Glaßer, Christian Reitwießner, Maximilian Witek

We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey.

Moreover, we show that 2-TSP is randomized $(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>>

Christian Glaßer, Christian Reitwießner, Victor Selivanov

We study the shrinking and separation properties (two notions well-known in descriptive set theory) for NP and coNP and show that under reasonable complexity-theoretic assumptions, both properties do not hold for NP and the shrinking property does not hold for coNP. In particular we obtain the following results.

1. NP ... more >>>

Christian Glaßer, Heinz Schmitz, Victor Selivanov

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results:

1. The classes of ... more >>>

Christian Glaßer, Alan L. Selman, Liyu Zhang

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: Where does the implication [can(f) \le_m can(g) => f \le_s ... more >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Liyu Zhang

<p> We study the question of the existence of non-mitotic sets in NP. We show under various hypotheses that:</p>

<ul>

<li>1-tt-mitoticity and m-mitoticity differ on NP.</li>

<li>1-tt-reducibility and m-reducibility differ on NP.</li>

<li>There exist non-T-autoreducible sets in NP (by a result from Ambos-Spies, these sets are neither ...
more >>>

Christian Glaßer, Alan L. Selman, Stephen Travers, Klaus W. Wagner

This paper is motivated by the open question

whether the union of two disjoint NP-complete sets always is

NP-complete. We discover that such unions retain

much of the complexity of their single components. More precisely,

they are complete with respect to more general reducibilities.

Christian Glaßer, Stephen Travers

We propose the e-model for leaf languages which generalizes the known balanced and unbalanced concepts. Inspired by the neutral behavior of rejecting paths of NP machines, we allow transducers to output empty words.

The paper explains several advantages of the new model. A central aspect is that it allows us ... more >>>

Christian Glaßer, Alan L. Selman, Liyu Zhang

We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus.

more >>>Christian Glaßer, A. Pavan, Alan L. Selman, Liyu Zhang

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glasser et al., complete sets for all of the following complexity classes are m-mitotic: ... more >>>

Christian Glaßer, Stephen Travers, Klaus W. Wagner

We introduce the polynomial-time tree reducibility

(ptt-reducibility). Our main result states that for

languages $B$ and $C$ it holds that

$B$ ptt-reduces to $C$ if and only if

the unbalanced leaf-language class of $B$ is robustly contained in

the unbalanced leaf-language class of $C$.

...
more >>>

Christian Glaßer, Mitsunori Ogihara, A. Pavan, Alan L. Selman, Liyu Zhang

We show the following results regarding complete sets:

NP-complete sets and PSPACE-complete sets are many-one

autoreducible.

Complete sets of any level of PH, MODPH, or

the Boolean hierarchy over NP are many-one autoreducible.

EXP-complete sets are many-one mitotic.

NEXP-complete sets are weakly many-one mitotic.

PSPACE-complete sets are weakly Turing-mitotic.

... more >>>Christian Glaßer, Alan L. Selman, Liyu Zhang

We prove that every disjoint NP-pair is polynomial-time, many-one equivalent to

the canonical disjoint NP-pair of some propositional proof system. Therefore, the degree structure of the class of disjoint NP-pairs and of all canonical pairs is

identical. Secondly, we show that this degree structure is not superficial: Assuming there exist ...
more >>>

Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner

Given a fixed computable binary operation f, we study the complexity of the following generation problem: The input consists of strings a1,...,an,b. The question is whether b is in the closure of {a1,...,an} under operation f.

For several subclasses of operations we prove tight upper and lower bounds for the ... more >>>

Christian Glaßer, A. Pavan, Alan L. Selman, Samik Sengupta

We study several properties of sets that are complete for NP.

We prove that if $L$ is an NP-complete set and $S \not\supseteq L$ is a p-selective sparse set, then $L - S$ is many-one-hard for NP. We demonstrate existence of a sparse set $S \in \mathrm{DTIME}(2^{2^{n}})$

such ...
more >>>

Christian Glaßer

We study the power of balanced regular leaf-languages.

First, we investigate (i) regular languages that are

polylog-time reducible to languages in dot-depth 1/2 and

(ii) regular languages that are polylog-time decidable.

For both classes we provide

- forbidden-pattern characterizations, and

- characterizations in terms of regular expressions.

Both ... more >>>

Elmar Böhler, Christian Glaßer, Daniel Meister

SBP is a probabilistic promise class located

between MA and AM \cap BPPpath. The first

part of the paper studies the question of whether

SBP has many-one complete sets. We relate

this question to the existence of uniform

enumerations. We construct an oracle relative to

which SBP and AM do ...
more >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta

We prove that all of the following assertions are equivalent:

There is a many-one complete disjoint NP-pair;

there is a strongly many-one complete disjoint NP-pair;

there is a Turing complete disjoint NP-pair such that all reductions

are smart reductions;

there is a complete disjoint NP-pair for one-to-one, invertible ...
more >>>

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

We study the question of whether the class DisNP of

disjoint pairs (A, B) of NP-sets contains a complete pair.

The question relates to the question of whether optimal

proof systems exist, and we relate it to the previously

studied question of whether there exists ...
more >>>