Acceptor-Definable Counting Classes

Aggelos Kiayias, Aris Pagourtzis, Kiron Sharma, Stathis Zachos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.
Original languageEnglish
Title of host publicationAdvances in Informatics
Subtitle of host publication8th Panhellenic Conference on Informatics, PCI 2001 Nicosia, Cyprus, November 8--10, 2001 Revised Selected Papers
EditorsYannis Manolopoulos, Skevos Evripidou, Antonis C. Kakas
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Pages453-463
Number of pages11
ISBN (Electronic)978-3-540-38076-4
ISBN (Print)978-3-540-07544-8
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume2563
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Acceptor-Definable Counting Classes'. Together they form a unique fingerprint.

Cite this