In this survey we describe progress over the last decade or so in understanding the complexity of solving constraint satisfaction problems (CSPs) approximately in the streaming and sketching models of computation. After surveying some of the results we give some sketches of the proofs and in particular try to explain why there is a tight dichotomy result for sketching algorithms working in subpolynomial space regime.

翻译：在这次调查中,我们描述了过去十年左右在理解约在计算流模式和草图模型中解决约束性满意度问题的复杂性方面取得的进展。 在对一些结果进行考察之后,我们给出了一些证据的草图,特别是试图解释为什么在亚极空间体系下工作的草图算法会产生严格的二分法结果。