Thursday, January 12, 2017

Has the Feder-Vardi dichotomy conjecture been proved?

The Feder-Vardi dichotomy conjecture (which, as far as I know, stems from this 1998 article) is a celebrated open problem in the study of the complexity of constraint satisfaction problems (CSPs). It states that, for every finite relational structure, the set of all CSPs that can be represented using only relations chosen from that set is either in P or is NP-complete.

A paper claiming a solution to the Feder-Vardi  conjecture appeared yesterday on the arXiv:

https://arxiv.org/abs/1701.02409

Tómas Feder is the third author. (However, I noticed that the order of the authors in the version of the paper Feder posted on his web page is different from the one used in the arXiv version.)

The authors have also posted two videos on YouTube:

https://youtu.be/PBX51Qv5wtw
https://youtu.be/vD68km24Rh0

If the technical content of the paper is found to be correct by the community working on CSPs after careful peer review, this is a truly major result.

No comments: