A Probabilistic Approach to the Dichotomy Problem
From MaRDI portal
Publication:3446822
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)
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
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)