Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly.
Gillat KolDmitry ParamonovRaghuvansh R. SaxenaHuacheng YuPublished in: ITCS (2023)
Keyphrases
- constraint satisfaction problems
- data streams
- backtracking algorithm
- real valued
- constraint problems
- constraint satisfaction
- partial constraint satisfaction
- solving constraint satisfaction problems
- constraint programming
- real time
- constraint propagation
- space complexity
- boolean functions
- configuration problems
- sat encodings
- non binary
- worst case
- search space
- computational complexity
- genetic algorithm