Details

Autor(en) / Beteiligte

• Manolopoulos, Yannis
• Evripidou, Skevos
• Kakas, Antonis C

Titel

Acceptor-Definable Counting Classes

Ist Teil von

• Advances in Informatics, 2003, Vol.2563, p.453-463

Ort / Verlag

Germany: Springer Berlin / Heidelberg

Erscheinungsjahr

2003

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

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