On the complexity of trial and error for constraint satisfaction problems

DOI10.1016/j.jcss.2017.07.005zbMath1382.68114arXiv1406.5336OpenAlexW1665954832MaRDI QIDQ1678168

Miklos Santha, Raghav Kulkarni, Youming Qiao, Aarthi Sundaram, Gábor Ivanyos

Publication date: 14 November 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityconstraint satisfaction problemstrial and error

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Noncrossing Subgraphs in Topological Layouts
• Solving Linear Programming with Constraints Unknown
• On the power of unique 2-prover 1-round games
• On Restricted Two-Factors
• On the Complexity of Trial and Error for Constraint Satisfaction Problems
• The complexity of satisfiability problems
• On the complexity of trial and error

This page was built for publication: On the complexity of trial and error for constraint satisfaction problems