Copertina

Separation of PSPACE and EXP

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Czerwinski, Reiner
Natura:	Preprint
Pubblicazione:	2021
Soggetti:	Computational Complexity 68Q15, 03D15 F.1.3; F.2.3
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Polynomial Hierarchy does not collapse
di: Czerwinski, Reiner
Pubblicazione: (2024)

NP-hard problems are not in BQP
di: Czerwinski, Reiner
Pubblicazione: (2023)

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

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

Oracle Separations for RPH
di: Hamm, Thekla, et al.
Pubblicazione: (2025)

Meta Theorem for Hardness on FCP-Problem
di: Nagao, Atsuki, et al.
Pubblicazione: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
di: Hirsch, Edward A., et al.
Pubblicazione: (2025)

Linear Matroid Intersection is in Catalytic Logspace
di: Agarwala, Aryan, et al.
Pubblicazione: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
di: Göös, Mika, et al.
Pubblicazione: (2025)

A Note on Avoid vs MCSP
di: Hirsch, Edward A., et al.
Pubblicazione: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
di: Garcia, Baruch
Pubblicazione: (2026)

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

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

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
di: Bodnar, Levente
Pubblicazione: (2024)

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

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
di: Rossman, Benjamin
Pubblicazione: (2024)

The Solver's Paradox in Formal Problem Spaces
di: Rosko, Milan
Pubblicazione: (2025)

Quantum Sabotage Complexity
di: Cornelissen, Arjan, et al.
Pubblicazione: (2024)

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

Quoridor is PSPACE-Complete
di: Drop, Marius, et al.
Pubblicazione: (2026)

Failure of the strong feasible disjunction property
di: Krajicek, Jan
Pubblicazione: (2026)

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

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

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
di: Lela, Marko
Pubblicazione: (2025)

The Optimizer Quotient and the Certification Trilemma
di: Simas, Tristan
Pubblicazione: (2026)

Generalisations of Matrix Partitions : Complexity and Obstructions
di: Barsukov, Alexey, et al.
Pubblicazione: (2021)

On the computational complexity of Data Flow Analysis
di: Sood, Gaurav, et al.
Pubblicazione: (2013)

The Serial Scaling Hypothesis
di: Liu, Yuxi, et al.
Pubblicazione: (2025)

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

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
di: Shalunov, Yakov
Pubblicazione: (2023)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
di: Saffidine, Abdallah, et al.
Pubblicazione: (2025)

Adversarial Barrier in Uniform Class Separation
di: Rosko, Milan
Pubblicazione: (2025)

Evolomino is NP-complete
di: Nikolaev, Andrei V.
Pubblicazione: (2025)

Dichotomy for orderings?
di: Kun, Gábor, et al.
Pubblicazione: (2025)

Hive is PSPACE-Hard
di: Andel, Daniël, et al.
Pubblicazione: (2025)

A Homological Separation of $\mathbf{P}$ from $\mathbf{NP}$ via Computational Topology and Category Theory
di: Tang, Jian-Gang
Pubblicazione: (2025)

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

A proof complexity conjecture and the Incompleteness theorem
di: Krajicek, Jan
Pubblicazione: (2023)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
di: Lin, Tianrong
Pubblicazione: (2024)

On the Descriptive Complexity of Groups without Abelian Normal Subgroups
di: Grochow, Joshua A., et al.
Pubblicazione: (2022)