Cover Image

Limit on the computational power of $\mathrm{C}$-random strings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Milovanov, Alexey
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

On the power of counting the total number of computation paths of NPTMs
by: Bakali, Eleni, et al.
Published: (2023)

An Oracle with no $\mathrm{UP}$-Complete Sets, but $\mathrm{NP}=\mathrm{PSPACE}$
by: Dingel, David, et al.
Published: (2024)

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)

PLS-completeness of string permutations
by: Scheder, Dominik, et al.
Published: (2025)

On the power of adaption and randomization
by: Krieg, David, et al.
Published: (2024)

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
by: Mitosek, Piotr
Published: (2024)

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)

Identifying Codes Kernelization Limitations
by: Banik, Aritra, et al.
Published: (2025)

Towards infinite PCSP: a dichotomy for monochromatic cliques
by: Banakh, Demian, et al.
Published: (2026)

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)

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)

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

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

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

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
by: Lichter, Moritz, et al.
Published: (2024)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
by: Yung, Kingsley
Published: (2024)

Canonization of a random graph by two matrix-vector multiplications
by: Verbitsky, Oleg, et al.
Published: (2023)

Limit-sure reachability for small memory policies in POMDPs is NP-complete
by: Asadi, Ali, et al.
Published: (2024)

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

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

On guarded extensions of MMSNP
by: Barsukov, Alexey, et al.
Published: (2023)

$\mathrm{TIME}[t]\subseteq \mathrm{SPACE}[O(\sqrt{t})]$ via Tree Height Compression
by: Nye, Logan
Published: (2025)

Limits of structures and Total NP Search Problems
by: Ježil, Ondřej
Published: (2023)

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)

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

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

Quantum computation with indefinite causal structures
by: Araújo, Mateus, et al.
Published: (2017)

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

The Limits of Tractable Marginalization
by: Broadrick, Oliver, et al.
Published: (2025)

On the clustering of Padé zeros and poles of random power series
by: Dostoglou, Stamatis, et al.
Published: (2024)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

Time complexity for deterministic string machines
by: Cataltepe, Ali, et al.
Published: (2024)

Is a LOCAL algorithm computable?
by: Cruciani, Antonio, et al.
Published: (2026)