On the power of counting the total number of computation paths of NPTMs
From MaRDI portal
Publication:6636085
DOI10.1007/978-981-97-2340-9_18MaRDI QIDQ6636085
Stathis Zachos, Eleni Bakali, Aggeliki Chalki, Aris Pagourtzis, Sotiris Kanellopoulos
Publication date: 12 November 2024
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Relations among MOD-classes
- NP is as easy as detecting unique solutions
- Graph isomorphism is in the low hierarchy
- Relative complexity of checking and evaluating
- Gap-definable counting classes
- Upward separation for FewP and related classes
- Characterizations and approximability of hard counting classes below \#\textsf{P}
- Completeness, approximability and exponential time results for counting problems with easy decision version
- A complexity theory for feasible closure properties
- Graph Isomorphism is in SPP
- PP is as Hard as the Polynomial-Time Hierarchy
- Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs
- Estimating the Efficiency of Backtrack Programs
- Computational Complexity of Probabilistic Turing Machines
- Tree Size by Partial Backtracking
- P-Printable Sets
- On the power of parity polynomial time
- Graph isomorphism in quasipolynomial time [extended abstract]
- The Complexity of Counting Functions with Easy Decision Version
- Counting classes: Thresholds, parity, mods, and fewness
- Counting computations with formulae: logical characterisations of counting complexity classes
This page was built for publication: On the power of counting the total number of computation paths of NPTMs
