A FINER REDUCTION OF CONSTRAINT PROBLEMS TO DIGRAPHS

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10330772" target="_blank" >RIV/00216208:11320/16:10330772 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

A FINER REDUCTION OF CONSTRAINT PROBLEMS TO DIGRAPHS

Original language description

It is well known that the constraint satisfaction problem over a general relational structure A is polynomial time equivalent to the constraint problem over some associated digraph. We present a variant of this construction and show that the corresponding constraint satisfaction problem is logspace equivalent to that over A. Moreover, we show that almost all of the commonly encountered polymorphism properties are held equivalently on the A and the constructed digraph. As a consequence, the Algebraic CSP dichotomy conjecture as well as the conjectures characterizing CSPs solvable in logspace and in nondeterministic logspace are equivalent to their restriction to digraphs.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/GA13-01832S" target="_blank" >GA13-01832S: General algebra and its connections to computer science</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Logical Methods in Computer Science

ISSN

1860-5974

e-ISSN

—

Volume of the periodical

2015

Issue of the periodical within the volume

11

Country of publishing house

DE - GERMANY

Number of pages

33

Pages from-to

1-33

UT code for WoS article

—

EID of the result in the Scopus database

2-s2.0-84957922158