A Probabilistic Approach to the Dichotomy Problem

DOI10.1137/S0097539703435492zbMath1120.68059MaRDI QIDQ3446822

Tomasz Łuczak, Jaroslav Nešetřil

Publication date: 26 June 2007

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

projectivityrandom relationConstraint Satisfaction Problem (CSP)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Relational systems, laws of composition (08A02) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (5)

Tractability in constraint satisfaction problems: a survey ⋮ Forbidden lifts (NP and CSP for combinatorialists) ⋮ Many Facets of Dualities ⋮ Rigid binary relations on a 4-element domain ⋮ A surprising permanence of old motivations (a not-so-rigid story)

This page was built for publication: A Probabilistic Approach to the Dichotomy Problem