The Polynomial Hierarchy does not collapse

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Czerwinski, Reiner
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Formal Languages and Automata Theory 03D15, 03D55, 69Q15, 68Q17 F.1.3; F.2.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Run supports and initial algebra supports of weighted automata
by: Droste, Manfred, et al.
Published: (2024)

Languages given by Finite Automata over the Unary Alphabet
by: Czerwiński, Wojciech, et al.
Published: (2023)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

Decision Problems on Copying and Shuffling
by: Halava, Vesa, et al.
Published: (2023)

A correspondence between the time and space complexity
by: Latkin, Ivan V.
Published: (2023)

$\mathbb{N}$-polyregular functions arise from well-quasi-orderings
by: Lopez, Aliaume
Published: (2024)

A Formalization of Co-Transcriptional Splicing as an Operation on Formal Languages
by: Cho, Da-Jung, et al.
Published: (2025)

Evaluating Massively Parallel Algorithms for DFA Minimisation, Equivalence Checking and Inclusion Checking
by: Heemstra, Jan, et al.
Published: (2025)

Determination of the fifth Busy Beaver value
by: The bbchallenge Collaboration, et al.
Published: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

On Some Complexity Results for Even Linear Languages
by: Cojocaru, Liliana
Published: (2024)

Languages of Words of Low Automatic Complexity Are Hard to Compute
by: Chen, Joey, et al.
Published: (2025)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
by: Dörfler, Julian, et al.
Published: (2024)

Formalizing Computational Paths and Fundamental Groups in Lean
by: Ramos, Arthur F., et al.
Published: (2025)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Complexities of Well-Quasi-Ordered Substructural Logics
by: Galatos, Nikolaos, et al.
Published: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Word equations and the exponent of periodicity
by: Diekert, Volker, et al.
Published: (2025)

Regular Model Checking for Systems with Effectively Regular Reachability Relation
by: Esparza, Javier, et al.
Published: (2025)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
by: Bannach, Max, et al.
Published: (2025)

Multidimensional tilings and MSO logic
by: Pallen, Rémi, et al.
Published: (2025)

Subsets of groups with context-free preimages
by: Levine, Alex
Published: (2023)

The Optimizer Quotient and the Certification Trilemma
by: Simas, Tristan
Published: (2026)

Lindenmayer graph languages, first-order theories and expanders
by: Knapik, Teodor
Published: (2024)

Free inverse monoids are co-context-free
by: Brough, Tara Macalister, et al.
Published: (2025)

Why the classes P and NP are not well-defined finitarily
by: Anand, Bhupinder Singh
Published: (2024)

NL Is Strictly Contained in P
by: Flum, Santiago, et al.
Published: (2023)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

Truth-Aware Decoding: A Program-Logic Approach to Factual Language Generation
by: Alpay, Faruk, et al.
Published: (2025)

Solutions of Word Equations over Partially Commutative Structures
by: Diekert, Volker, et al.
Published: (2016)

Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)

Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata
by: Guillon, Bruno, et al.
Published: (2025)

Finite-Horizon First-Order Rank Profiles of Regular Languages
by: Bazarova, Madina, et al.
Published: (2026)

On the Intersection Problem for Quantum Finite Automata
by: Benso, Andrea, et al.
Published: (2024)