On the power of counting the total number of computation paths of NPTMs
From MaRDI portal
Publication:6636085
Cites work
- scientific article; zbMATH DE number 477971 (Why is no real title available?)
- scientific article; zbMATH DE number 1953880 (Why is no real title available?)
- scientific article; zbMATH DE number 3799016 (Why is no real title available?)
- A complexity theory for feasible closure properties
- Characterizations and approximability of hard counting classes below \#\textsf{P}
- Completeness, approximability and exponential time results for counting problems with easy decision version
- Computational Complexity of Probabilistic Turing Machines
- Counting classes: Thresholds, parity, mods, and fewness
- Counting computations with formulae: logical characterisations of counting complexity classes
- Descriptive complexity for counting complexity classes
- Estimating the Efficiency of Backtrack Programs
- Gap-definable counting classes
- Graph Isomorphism is in SPP
- Graph isomorphism in quasipolynomial time (extended abstract)
- Graph isomorphism is in the low hierarchy
- Heuristic Sampling: A Method for Predicting the Performance of Tree Searching Programs
- NP is as easy as detecting unique solutions
- On the power of parity polynomial time
- P-Printable Sets
- PP is as Hard as the Polynomial-Time Hierarchy
- Relations among MOD-classes
- Relative complexity of checking and evaluating
- The Complexity of Counting Functions with Easy Decision Version
- The complexity of computing the permanent
- Tree Size by Partial Backtracking
- Upward separation for FewP and related 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)
