Image de couverture de livre

Finitely (In)tractable Promise Constraint Satisfaction Problems

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Asimi, Kristina, Barto, Libor
Format:	Preprint
Publié:	2020
Sujets:	Computational Complexity Logic 68Q17 F.1.3
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
par: Susukita, Kosuke, et autres
Publié: (2026)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
par: Dorochko, Leonid, et autres
Publié: (2026)

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

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
par: Asimi, Kristina, et autres
Publié: (2024)

Shifted Partial Derivative Polynomial Rank and Codimension
par: Edwards, Darren J.
Publié: (2025)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
par: Rossman, Benjamin
Publié: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
par: Kelley, Zander, et autres
Publié: (2023)

Generalisations of Matrix Partitions : Complexity and Obstructions
par: Barsukov, Alexey, et autres
Publié: (2021)

The Solver's Paradox in Formal Problem Spaces
par: Rosko, Milan
Publié: (2025)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
par: Marković, Petar, et autres
Publié: (2026)

Failure of the strong feasible disjunction property
par: Krajicek, Jan
Publié: (2026)

Meta Theorem for Hardness on FCP-Problem
par: Nagao, Atsuki, et autres
Publié: (2025)

On the computational complexity of Data Flow Analysis
par: Sood, Gaurav, et autres
Publié: (2013)

NP-hardness of p-adic linear regression
par: Baker, Gregory D.
Publié: (2026)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
par: Huseynzade, Rafig
Publié: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
par: Hakoniemi, Tuomas, et autres
Publié: (2024)

A correspondence between the time and space complexity
par: Latkin, Ivan V.
Publié: (2023)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
par: Schewe, Klaus-Dieter
Publié: (2020)

I/O complexity and pebble games with partial computations
par: Sobczyk, Aleksandros
Publié: (2024)

Quoridor is PSPACE-Complete
par: Drop, Marius, et autres
Publié: (2026)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
par: Bodirsky, Manuel, et autres
Publié: (2024)

Upper and Lower Bounds for the Linear Ordering Principle
par: Hirsch, Edward A., et autres
Publié: (2025)

Linear Matroid Intersection is in Catalytic Logspace
par: Agarwala, Aryan, et autres
Publié: (2025)

Oracle Separations for RPH
par: Hamm, Thekla, et autres
Publié: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
par: Göös, Mika, et autres
Publié: (2025)

A Note on Avoid vs MCSP
par: Hirsch, Edward A., et autres
Publié: (2025)

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

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
par: Lela, Marko
Publié: (2025)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
par: von Liechtenstein, Maximilian R. P.
Publié: (2025)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
par: Saffidine, Abdallah, et autres
Publié: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
par: Bodnar, Levente
Publié: (2024)

Hive is PSPACE-Hard
par: Andel, Daniël, et autres
Publié: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
par: Kumar, Mrinal, et autres
Publié: (2018)

Completeness classes in algebraic complexity theory
par: Bürgisser, Peter
Publié: (2024)

Complexities of Well-Quasi-Ordered Substructural Logics
par: Galatos, Nikolaos, et autres
Publié: (2025)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
par: Ye, Lixi
Publié: (2026)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
par: Dörfler, Julian, et autres
Publié: (2024)

Quantum Time-Space Tradeoffs for Matrix Problems
par: Beame, Paul, et autres
Publié: (2024)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
par: Bodirsky, Manuel, et autres
Publié: (2023)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
par: Lela, Marko
Publié: (2025)