Copertina

Failure of the strong feasible disjunction property

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Krajicek, Jan
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity Logic O3F20, 68Q15 F.1.3; F.4.1
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Extended Nullstellensatz proof systems
di: Krajicek, Jan
Pubblicazione: (2023)

On the existence of strong proof complexity generators
di: Krajicek, Jan
Pubblicazione: (2022)

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

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

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

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

Strategies, model checking and branching-time properties in Maude
di: Rubio, Rubén, et al.
Pubblicazione: (2024)

Finitely (In)tractable Promise Constraint Satisfaction Problems
di: Asimi, Kristina, et al.
Pubblicazione: (2020)

On the Satisfaction Probabilities of $k$-CNF Formulas
di: Tantau, Till
Pubblicazione: (2022)

Model checking strategy-controlled systems in rewriting logic
di: Rubio, Rubén, et al.
Pubblicazione: (2024)

Metalevel transformation of strategies
di: Rubio, Rubén, et al.
Pubblicazione: (2024)

Simulating and model checking membrane systems using strategies in Maude
di: Rubio, Rubén, et al.
Pubblicazione: (2024)

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

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

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)

Oracle Separations for RPH
di: Hamm, Thekla, 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)

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

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
di: de Rezende, Susanna F., et al.
Pubblicazione: (2019)

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

Conformance Games for Graded Semantics
di: Forster, Jonas, et al.
Pubblicazione: (2024)

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)

Relative Constructibility via Generalised Sequential Algorithms
di: Lau, Desmond
Pubblicazione: (2024)

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

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

Separation of PSPACE and EXP
di: Czerwinski, Reiner
Pubblicazione: (2021)

Arithmetics within the Linear Time Hierarchy
di: Pollett, Chris
Pubblicazione: (2025)

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

A Logspace Constructive Proof of L=SL
di: Buss, Sam, et al.
Pubblicazione: (2025)

A Modular Lean 4 Framework for Confluence and Strong Normalization of Lambda Calculi with Products and Sums
di: Ramos, Arthur, et al.
Pubblicazione: (2025)

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

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

Propositional dynamic logic and asynchronous cascade decompositions for regular trace languages
di: Adsul, Bharat, et al.
Pubblicazione: (2024)

Constructibility and the P versus NP problem
di: Hole, Arne
Pubblicazione: (2024)

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

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