10 citations · 12 across the 9 of their papers we have counts for
5 papers · 1 filter
Towards infinite PCSP: a dichotomy for monochromatic cliques
Demian Banakh, Alexey Barsukov, Tamio-Vesa Nakajima
The logic MMSNP is a well-studied fragment of Existential Second-Order logic that, from a computational perspective, captures finite-domain Constraint Satisfaction Problems (CSPs)…
Hardness of linearly ordered 4-colouring of 3-colourable 3-uniform hypergraphs
Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal +2
A linearly ordered (LO) -colouring of a hypergraph is a colouring of its vertices with colours such that each edge contains a unique maximal colour. Deciding wheth…
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin +2
The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal problem can be…
On the complexity of symmetric vs. functional PCSPs
Tamio-Vesa Nakajima, Stanislav Živný
The complexity of the promise constraint satisfaction problem is largely unknown, even for symmetric and , exc…
Linearly ordered colourings of hypergraphs
Tamio-Vesa Nakajima, Stanislav Živný
A linearly ordered (LO) -colouring of an -uniform hypergraph assigns an integer from to every vertex so that, in every edge, the (multi)set of colours has…