:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Wild, Marcel
Format:	Preprint
Published:	2012
Subjects:	Computational Complexity 68Q25
Online Access:	https://arxiv.org/abs/1208.2559
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
by: Xia, Mingji
Published: (2026)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

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

Cluster Vertex Deletion Problems on Cubic Graphs
by: Rusu, Irena
Published: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
by: Avila, Tatiana Rocha, et al.
Published: (2026)

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

No Constant-Cost Protocol for Point--Line Incidence
by: Göös, Mika, et al.
Published: (2026)

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

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, 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)

The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)

On the Low Weight Polynomial Multiple Problem
by: Ţiplea, Ferucio Laurenţiu, et al.
Published: (2024)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

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

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

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

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

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

On the complexity of solving equations over the symmetric group $S_4$
by: Aichinger, Erhard, et al.
Published: (2025)

Linear average-case complexity of algorithmic problems in groups
by: Olshanskii, Alexander, et al.
Published: (2022)

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

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

Computational Complexity of Minimal Trap Spaces in Boolean Networks
by: Moon, Kyungduk, et al.
Published: (2022)

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

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

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

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

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

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

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

On the Complexity of Bipartite Degree Realizability
by: Miklós, István
Published: (2025)

Reduction of the group isomorphism problem to the group automorphism problem
by: Skresanov, Saveliy V.
Published: (2025)

Concurrency Constrained Scheduling with Tree-Like Constraints
by: Bodlaender, Hans L., et al.
Published: (2025)

Regenerative Ulam-von Neumann Algorithm: An Innovative Markov chain Monte Carlo Method for Matrix Inversion
by: Ghosh, Soumyadip, et al.
Published: (2024)

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

Which graph motif parameters count?
by: Bläser, Markus, et al.
Published: (2025)

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

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