On the power of counting the total number of computation paths of NPTMs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917799147864064 |
|---|---|
| author | Bakali, Eleni Chalki, Aggeliki Kanellopoulos, Sotiris Pagourtzis, Aris Zachos, Stathis |
| author_facet | Bakali, Eleni Chalki, Aggeliki Kanellopoulos, Sotiris Pagourtzis, Aris Zachos, Stathis |
| contents | In this paper, we define and study variants of several complexity classes of decision problems that are defined via some criteria on the number of accepting paths of an NPTM. In these variants, we modify the acceptance criteria so that they concern the total number of computation paths instead of the number of accepting ones. This direction reflects the relationship between the counting classes #P and TotP, which are the classes of functions that count the number of accepting paths and the total number of paths of NPTMs, respectively. The former is the well-studied class of counting versions of NP problems introduced by Valiant (1979). The latter contains all self-reducible counting problems in #P whose decision version is in P, among them prominent #P-complete problems such as Non-negative Permanent, #PerfMatch, and #DNF-Sat, thus playing a significant role in the study of approximable counting problems. We show that almost all classes introduced in this work coincide with their `#accepting paths'-definable counterparts, thus providing an alternative model of computation for them. Moreover, for each of these classes, we present a novel family of complete problems, which are defined via TotP-complete problems. This way, we show that all the aforementioned classes have complete problems that are defined via counting problems whose existence version is in P, in contrast to the standard way of obtaining completeness results via counting versions of NP-complete problems. To the best of our knowledge, prior to this work, such results were known only for parity-P and C=P. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_11614 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the power of counting the total number of computation paths of NPTMs Bakali, Eleni Chalki, Aggeliki Kanellopoulos, Sotiris Pagourtzis, Aris Zachos, Stathis Computational Complexity In this paper, we define and study variants of several complexity classes of decision problems that are defined via some criteria on the number of accepting paths of an NPTM. In these variants, we modify the acceptance criteria so that they concern the total number of computation paths instead of the number of accepting ones. This direction reflects the relationship between the counting classes #P and TotP, which are the classes of functions that count the number of accepting paths and the total number of paths of NPTMs, respectively. The former is the well-studied class of counting versions of NP problems introduced by Valiant (1979). The latter contains all self-reducible counting problems in #P whose decision version is in P, among them prominent #P-complete problems such as Non-negative Permanent, #PerfMatch, and #DNF-Sat, thus playing a significant role in the study of approximable counting problems. We show that almost all classes introduced in this work coincide with their `#accepting paths'-definable counterparts, thus providing an alternative model of computation for them. Moreover, for each of these classes, we present a novel family of complete problems, which are defined via TotP-complete problems. This way, we show that all the aforementioned classes have complete problems that are defined via counting problems whose existence version is in P, in contrast to the standard way of obtaining completeness results via counting versions of NP-complete problems. To the best of our knowledge, prior to this work, such results were known only for parity-P and C=P. |
| title | On the power of counting the total number of computation paths of NPTMs |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2306.11614 |