Ineffectiveness for Search and Undecidability of PCSP Meta-Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Larrauri, Alberto
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Computation and Language Data Structures and Algorithms Logic in Computer Science 68Q17, 68Q25
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
by: Cui, Jinchuan, et al.
Published: (2022)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
by: Kátay, Tamás, et al.
Published: (2023)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
by: Jain, Rahul, et al.
Published: (2019)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Parallel Algorithms for Group Isomorphism via Code Equivalence
by: Levet, Michael
Published: (2026)

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases
by: Meusel, Julia, et al.
Published: (2025)

On Binary Networked Public Goods Game with Altruism
by: Maiti, Arnab, et al.
Published: (2022)

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

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Treewidth Inapproximability and Tight ETH Lower Bound
by: Bonnet, Édouard
Published: (2024)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
by: Datta, Swarnalipa, et al.
Published: (2026)

Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Answering Related Questions
by: Bonnet, Édouard
Published: (2025)

Coloring Hardness on Low Twin-Width Graphs
by: Bonnet, Édouard
Published: (2025)

Computational Complexity of Model-Checking Quantum Pushdown Systems
by: Lin, Deren, et al.
Published: (2025)

Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph
by: Li, Xingfu, et al.
Published: (2026)

Exact and Approximate High-Multiplicity Scheduling on Identical Machines
by: Jansen, Klaus, et al.
Published: (2024)

A Physical Analogy between Molecular Ordering and SAT-to-Ising Annealing
by: Dubey, ShivKishan, et al.
Published: (2025)

Group Order Logic
by: Dahan, Anatole
Published: (2025)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
by: Li, Zhangsong
Published: (2026)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
by: DasGupta, Bhaskar, et al.
Published: (2026)

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

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

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