Cover Image

On the power of counting the total number of computation paths of NPTMs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bakali, Eleni, Chalki, Aggeliki, Kanellopoulos, Sotiris, Pagourtzis, Aris, Zachos, Stathis
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Satisfactory Budget Division
by: Gourvès, Laurent, et al.
Published: (2025)

Finite Pinwheel Scheduling: the k-Visits Problem
by: Kanellopoulos, Sotiris, et al.
Published: (2025)

On the computational power of $C$-random strings
by: Milovanov, Alexey
Published: (2024)

Limit on the computational power of $\mathrm{C}$-random strings
by: Milovanov, Alexey
Published: (2026)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
by: Colli, Giordano
Published: (2025)

The computational power of discrete chemical reaction networks with bounded executions
by: Doty, David, et al.
Published: (2024)

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

Complexity classification of counting graph homomorphisms modulo a prime number
by: Bulatov, Andrei A., et al.
Published: (2021)

On the complexity of computing Strahler numbers
by: Ganardi, Moses, et al.
Published: (2025)

Monotone Contractions
by: Batziou, Eleni, et al.
Published: (2024)

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

Time hierarchies for sublogarithmic-space quantum computation
by: Say, A. C. Cem
Published: (2025)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

Beer Path Problems in Temporal Graphs
by: D'Ascenzo, Andrea, et al.
Published: (2025)

The Complexity of Deciding Characteristic Formulae Modulo Nested Simulation (extended abstract)
by: Aceto, Luca, et al.
Published: (2025)

Deciding characteristic formulae: A journey in the branching-time spectrum
by: Aceto, Luca, et al.
Published: (2025)

The complexity of deciding characteristic formulae in van Glabbeek's branching-time spectrum
by: Aceto, Luca, et al.
Published: (2024)

On the Computation of Equilibria in Discrete First-Price Auctions
by: Filos-Ratsikas, Aris, et al.
Published: (2024)

Equilibrium Computation in First-Price Auctions with Correlated Priors
by: Filos-Ratsikas, Aris, et al.
Published: (2025)

The complexity of convexity number and percolation time in the cycle convexity
by: Lima, Carlos V. G. C., et al.
Published: (2024)

Directed disjoint paths remains W[1]-hard on acyclic digraphs without large grid minors
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

A computing machinery using a continuous memory tape
by: Oktar, Yigit
Published: (2023)

Man, these New York Times games are hard! A computational perspective
by: Alberti, Alessandro Giovanni, et al.
Published: (2025)

Fast polynomial computations with space constraints
by: Grenet, Bruno
Published: (2025)

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

Quantum algorithms for path and cycle containment problems
by: Cornelissen, Arjan, et al.
Published: (2026)

Recursion and proof theoretical characterizations of small circuit classes with modulo counting via discrete differential equations (long version)
by: Antonelli, Melissa, et al.
Published: (2026)

Precoloring extension with demands on paths
by: Das, Arun Kumar, et al.
Published: (2025)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

Stochastic thermodynamics of computation
by: Wolpert, David H.
Published: (2019)

Quantum embedding of graphs for subgraph counting
by: Adhikari, Bibhas
Published: (2026)

The Borsuk number of a graph
by: Cáceres, José, et al.
Published: (2026)

Efficient derandomization of differentially private counting queries
by: Ghentiyala, Surendra
Published: (2025)

The power of quantum circuits in sampling
by: Blanc, Guy, et al.
Published: (2025)

QBF Merge Resolution is powerful but unnatural
by: Mahajan, Meena, et al.
Published: (2022)

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Geometric and computational hardness of bilevel programming
by: Bolte, Jérôme, et al.
Published: (2024)