Random MAX SAT, random MAX CUT, and their phase transitions
Random MAX SAT, random MAX CUT, and their phase transitions
复制标题
DOI：
10.1002/rsa.20015
复制
发表时间：
2004-07-01
影响因子：
1
通讯作者：
Sorkin, GB
中科院分区：
文献类型：
--
作者：
Coppersmith, D;Gamarnik, D;Sorkin, GB
在随机输入的情况下，某些决策问题会经历一个“相变”。我们在优化环境中证明了类似的行为。给出一个关于n个变量和m个k-变量子句的合取范式(CNF)公式F，用max F表示单次变量赋值可满足的子句的最大数目。(因此，判定问题k-SAT就是确定max F是否等于m。)在随机选取公式F的情况下，最大值F的期望由小于或等于E max F小于或等于m的(314)m平凡有界.我们证明了对于m=[Cn]子句的随机公式：对于常数c<；1，Emax F是[Cn]-Theta(1/n)；对于大的c，它逼近((3/4)c+Theta(Rootc))n；在“窗口”c=i+Theta(n(-1/3))中，它是Cn-Theta(1).我们的全部结果更加详细，但这已经表明优化问题Max 2-SAT和2-SAT决策问题一样经历了一个相变，并且在相同的临界值c=1处。我们的大多数结果是在没有参考决策2-SAT的类似命题的情况下建立的，并且可以用于复制它们。我们考虑Max 2-SAT的在线版本，并且表明对于一个版本，明显的贪婪算法是最优的；所有其他自然问题仍然是开放的。我们只能把我们最简单的Max 2-SAT结果推广到Max k-SAT，但是我们猜想一个类似于民间传说“可满足性阈值猜想”的“Max k-SAT极限函数猜想”，但即使对k=2也是开放的。这两个猜想都不会立即暗示另一个猜想，但进一步猜测它们之间的联系是很自然的。我们还证明了随机最大割的类似结果。(C)2004年威利期刊公司。
With random inputs, certain decision problems undergo a "phase transition." We prove similar behavior in an optimization context. Given a conjunctive normal form (CNF) formula F on n variables and with m k-variable clauses, denote by max F the maximum number of clauses satisfiable by a single assignment of the variables. (Thus the decision problem k-SAT is to determine if max F is equal to m.) With the formula F chosen at random, the expectation of max F is trivially bounded by (314)m less than or equal to E max F less than or equal to m. We prove that for random formulas with m = [cn] clauses: for constants c < 1, E max F is [cn] - Theta(1/n); for large c, it approaches ((3/4)c + Theta(rootc))n; and in the "window" c = I + Theta(n(-1/3)), it is Cn - Theta(1). Our full results are more detailed, but this already shows that the optimization problem MAX 2-SAT undergoes a phase transition just as the 2-SAT decision problem does, and at the same critical value c = 1. Most of our results are established without reference to the analogous propositions for decision 2-SAT, and can be used to reproduce them.We consider "online" versions Of MAX 2-SAT, and show that for one version the obvious greedy algorithm is optimal; all other natural questions remain open. We can extend only our simplest MAX 2-SAT results to MAX k-SAT, but we conjecture a "MAX k-SAT limiting function conjecture" analogous to the folklore "satisfiability threshold conjecture," but open even for k = 2. Neither conjecture immediately implies the other, but it is natural to further conjecture a connection between them. We also prove analogous results for random MAX CUT. (C) 2004 Wiley Periodicals, Inc.