期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1 [ k c s ] PSPACE provided s c ( 62 − o (1)) k 2 k , resolving a question of Austrin, Håstad, and Pass. Here MIP1 [ k c s ] is the class of languages decidable with completeness c and soundness s by an interactive proof system with k provers, each constrained to communicate just 1 bit.
关键词：Removed ridiculous spurious opening line in which I was testing an alternative to the LaTeX xspace package!
