Effective guessing has unlikely consequences
From MaRDI portal
Publication:6109068
DOI10.1007/s00224-023-10119-xarXiv2111.02138OpenAlexW3210010299MaRDI QIDQ6109068
András Z. Salamon, Michael Wehar
Publication date: 26 July 2023
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2111.02138
computational complexitylimited nondeterminismstructural complexitycomplexity class containmentseffective guessing
Cites Work
- Unnamed Item
- A Turing machine time hierarchy
- Computability and complexity theory.
- Turing machines that take advice
- Lower bounds on the complexity of recognizing SAT by Turing machines
- Time- and tape-bounded Turing acceptors and AFLs
- Nonuniform ACC Circuit Lower Bounds
- A Remark on Stirling's Formula
- Hierarchies for semantic classes
- Satisfiability Is Quasilinear Complete in NQL
- Reducibility among Combinatorial Problems
- On the Computational Complexity of Algorithms
- New non-uniform lower bounds for uniform classes
- Two-Tape Simulation of Multitape Turing Machines
- The complexity of theorem-proving procedures