TY - GEN

T1 - Acceptor-Definable Counting Classes

AU - Kiayias, Aggelos

AU - Pagourtzis, Aris

AU - Sharma, Kiron

AU - Zachos, Stathis

PY - 2003

Y1 - 2003

N2 - Counting functions that can be defined on non-deterministic acceptors (Turing machines without output), as opposed to those defined by transducers (Turing machines with output), have attracted much interest since 1979, when Valiant introduced the important class #P [19]. Apart from #P, several such classes have been defined in the literature [2], [5], [3], [12], [6]. Here we study the path-order complexity classes RAP, LAP and MAP, introduced in [6], which consist of functions that output the order of the rightmost, leftmost and middle accepting computation path (respectively) of a polynomial-time non-deterministic Turing acceptor (PNTM). We also consider TotP [6], the class of functions that output the total number of paths of a PNTM. We show several properties of these classes. In particular we prove that RAP and LAP are are equivalent under the Cook[1] sense with #P and TotP. This implies that all these classes are equally powerful when used as oracles to a polynomial computation, even if only one query is allowed. We also show that problems #perfect matchings and #dnf-sat are complete for RAP and LAP in the Cook[1] sense and for MAP in the Cook sense. Path-order classes give rise to corresponding path-order operators; these operators applied on the class NP provide alternative characterizations for known classes of optimization problems. Using these characterizations, we present natural complete problems for optimization classes.

AB - Counting functions that can be defined on non-deterministic acceptors (Turing machines without output), as opposed to those defined by transducers (Turing machines with output), have attracted much interest since 1979, when Valiant introduced the important class #P [19]. Apart from #P, several such classes have been defined in the literature [2], [5], [3], [12], [6]. Here we study the path-order complexity classes RAP, LAP and MAP, introduced in [6], which consist of functions that output the order of the rightmost, leftmost and middle accepting computation path (respectively) of a polynomial-time non-deterministic Turing acceptor (PNTM). We also consider TotP [6], the class of functions that output the total number of paths of a PNTM. We show several properties of these classes. In particular we prove that RAP and LAP are are equivalent under the Cook[1] sense with #P and TotP. This implies that all these classes are equally powerful when used as oracles to a polynomial computation, even if only one query is allowed. We also show that problems #perfect matchings and #dnf-sat are complete for RAP and LAP in the Cook[1] sense and for MAP in the Cook sense. Path-order classes give rise to corresponding path-order operators; these operators applied on the class NP provide alternative characterizations for known classes of optimization problems. Using these characterizations, we present natural complete problems for optimization classes.

U2 - 10.1007/3-540-38076-0_29

DO - 10.1007/3-540-38076-0_29

M3 - Conference contribution

SN - 978-3-540-07544-8

T3 - Lecture Notes in Computer Science

SP - 453

EP - 463

BT - Advances in Informatics

A2 - Manolopoulos, Yannis

A2 - Evripidou, Skevos

A2 - Kakas, Antonis C.

PB - Springer Berlin Heidelberg

CY - Berlin, Heidelberg

ER -