Abstract argumentation frameworks (AFs), originally proposed by Dung, constitute a central
formal model for the study of computational aspects of argumentation in AI. Credulous and …

Polynomial time machines having restricted access to an NP oracle are investigated.
Restricted access means that the number of queries to the oracle is restricted or the way in …

This book is an accessible introduction to complexity theory and cryptology, two closely
related areas in theoretical computer science. Based on courses taught at Heinrich-Heine …

1 Her work has been supported in part by an NRW grant for gender-sensitive universities
supporting her as a junior professor for Computational Social Choice and by the project …

In 1876, Lewis Carroll proposed a voting system in which the winner is the candidate who
with the fewest changes in voters' preferences becomes a Condorcet winner—a candidate …

Starting from NP-complete problems defined by questions of the kind 'max…⩾ m?'and
'min…⩽ m?'we consider problems defined by more complicated questions about these …

The polynomial hierarchy, composed of the levels P, NP, PNP, NPNP, etc., plays a central
role in classifying the complexity of feasible computations. It is not known whether the …

In this paper, we study the complexity of sets formed by boolean operations (union,
intersection, and complement) on NP sets. These are the sets accepted by trees of hardware …

This paper comprises a systematic comparison of several complexity classes of functions
that are computed nondeterministically in polynomial time or with an oracle in NP. There are …

We show that polynomial time truth-table reducibility via Boolean circuits to SAT is the same
as logspace truth-table reducibility via Boolean formulas to SAT and the same as logspace …