Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly.
Gillat KolDmitry ParamonovRaghuvansh SaxenaHuacheng YuPublished in: Electron. Colloquium Comput. Complex. (2022)
Keyphrases
- constraint problems
- constraint satisfaction problems
- backtracking algorithm
- constraint satisfaction
- real time
- partial constraint satisfaction
- constraint propagation
- computational complexity
- data streams
- worst case
- combinatorial optimization
- solving constraint satisfaction problems
- dynamic constraint satisfaction problems
- configuration problems
- space complexity
- boolean functions
- real valued
- search space