Zobrazeno 1 - 10
of 81
pro vyhledávání: '"Kozik, Marcin"'
We give a new, direct proof of the tetrachotomy classification for the model-checking problem of positive equality-free logic parameterised by the model. The four complexity classes are Logspace, NP-complete, co-NP-complete and Pspace-complete. The p
Externí odkaz:
http://arxiv.org/abs/2408.13840
Autor:
Banakh, Demian, Kozik, Marcin
We present a template for the Promise Constraint Satisfaction Problem (PCSP) which is NP-hard but does not satisfy the current state-of-the-art hardness condition [ACMTCT'21]. We introduce a new "injective" condition based on the smooth version of th
Externí odkaz:
http://arxiv.org/abs/2405.10774
We investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters or orbits, every finite structure. Our results generalize several theo
Externí odkaz:
http://arxiv.org/abs/2302.12112
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 solved in polynomial time. In the present work, we investigate this co
Externí odkaz:
http://arxiv.org/abs/2302.03456
Autor:
Barto, Libor, Kozik, Marcin
A value of a CSP instance is typically defined as a fraction of constraints that can be simultaneously met. We propose an alternative definition of a value of an instance and show that, for purely combinatorial reasons, a value of an unsolvable insta
Externí odkaz:
http://arxiv.org/abs/2107.09423
Publikováno v:
TheoretiCS, Volume 3 (May 15, 2024) theoretics:11361
This paper focuses on the algebraic theory underlying the study of the complexity and the algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend parts of the three approaches that have been developed to study the CSP
Externí odkaz:
http://arxiv.org/abs/2104.11808
We investigate the impact of modifying the constraining relations of a Constraint Satisfaction Problem (CSP) instance, with a fixed template, on the set of solutions of the instance. More precisely we investigate sensitive instances: an instance of t
Externí odkaz:
http://arxiv.org/abs/2005.00266
A PCSP is a combination of two CSPs defined by two similar templates; the computational question is to distinguish a YES instance of the first one from a NO instance of the second. The computational complexity of many PCSPs remains unknown. Even the
Externí odkaz:
http://arxiv.org/abs/1904.12424
Autor:
Dalmau, Víctor, Kozik, Marcin, Krokhin, Andrei, Makarychev, Konstantin, Makarychev, Yury, Opršal, Jakub
An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimiz
Externí odkaz:
http://arxiv.org/abs/1607.04787
Autor:
Kozik, Marcin
The characterization of all the Constraint Satisfaction Problems of bounded width, proposed by Feder and Vardi [SICOMP'98], was confirmed in [Bulatov'09] and independently in [FOCS'09, JACM'14]. Both proofs are based on the (2,3)-consistency (using P
Externí odkaz:
http://arxiv.org/abs/1605.00565