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

Konstantin Pervyshev

A polynomial time hierarchy for ZPTime with one bit of advice is proved. That is for any constants a and b such that 1 < a < b, ZPTime[n^a]/1 \subsetneq ZPTime[n^b]/1.

The technique introduced in this paper is very general and gives the same hierarchy for NTime \cap coNTime, UTime, ... more >>>

Dieter van Melkebeek, Konstantin Pervyshev

We show that for any reasonable semantic model of computation and for

any positive integer $a$ and rationals $1 \leq c < d$, there exists a language

computable in time $n^d$ with $a$ bits of advice but not in time $n^c$

with $a$ bits of advice. A semantic ...
more >>>

Jeff Kinne, Dieter van Melkebeek

We prove space hierarchy and separation results for randomized and other semantic models of computation with advice. Previous works on hierarchy and separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource. Our main theorems are the following.

Let <i>s</i>(<i>n</i>) ... more >>>

Zenon Sadowski

We investigate the connection between optimal propositional

proof systems and complete languages for promise classes.

We prove that an optimal propositional proof system exists

if and only if there exists a propositional proof system

in which every promise class with the test set in co-NP

...
more >>>

Olaf Beyersdorff, Zenon Sadowski

In this paper we investigate the following two questions:

Q1: Do there exist optimal proof systems for a given language L?

Q2: Do there exist complete problems for a given promise class C?

For concrete languages L (such as TAUT or SAT and concrete promise classes C (such as NP ... more >>>