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 QIDQ6636085FDOQ6636085
Authors: Eleni Bakali, Aggeliki Chalki, Sotiris Kanellopoulos, Aris Pagourtzis, Stathis Zachos 
Publication date: 12 November 2024
Cites Work
- The complexity of computing the permanent
- Title not available (Why is that?)
- Computational Complexity of Probabilistic Turing Machines
- NP is as easy as detecting unique solutions
- PP is as Hard as the Polynomial-Time Hierarchy
- Graph Isomorphism is in SPP
- Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs
- Estimating the Efficiency of Backtrack Programs
- Graph isomorphism is in the low hierarchy
- Title not available (Why is that?)
- Relative complexity of checking and evaluating
- Tree Size by Partial Backtracking
- Counting classes: Thresholds, parity, mods, and fewness
- Gap-definable counting classes
- A complexity theory for feasible closure properties
- Graph isomorphism in quasipolynomial time (extended abstract)
- P-Printable Sets
- Upward separation for FewP and related classes
- Relations among MOD-classes
- The Complexity of Counting Functions with Easy Decision Version
- On the power of parity polynomial time
- Characterizations and approximability of hard counting classes below \#\textsf{P}
- Completeness, approximability and exponential time results for counting problems with easy decision version
- Title not available (Why is that?)
- Descriptive complexity for counting complexity classes
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6636085)
