A Definability Dichotomy for Finite Valued CSPs

DOI10.4230/LIPIcs.CSL.2015.60zbMath1373.68264arXiv1504.03543MaRDI QIDQ5351950

Anuj Dawar, Pengming Wang

Publication date: 31 August 2017

Full work available at URL: https://arxiv.org/abs/1504.03543

zbMATH Keywords

optimization; definability; constraint satisfaction; descriptive complexity; fixed-point logic

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C60: Abstract computational complexity for mathematical programming problems

68Q19: Descriptive complexity and finite models

Related Items

Unnamed Item, Definable Inapproximability: New Challenges for Duplicator