zbMATH — the first resource for mathematics

A tighter upper bound for random MAX \(2\)-SAT. (English) Zbl 1260.68164
Summary: Given a conjunctive normal form \(F\) with \(n\) variables and \(m=cn\) \(2\)-clauses, it is interesting to study the maximum number \(\max F\) of clauses satisfied by all the assignments of the variables (MAX \(2\)-SAT). When \(c\) is sufficiently large, the upper bound of \(f(n,cn)=\mathbb{E}(\max F)\) of random MAX \(2\)-SAT had been derived by the first-moment argument. In this paper, we provide a tighter upper bound \((3/4)cn+g(c)cn\) also using the first-moment argument but correcting the error items for \(f(n,cn)\), and \(g(c)=(3/4)\cos((1/3)\times\arccos((4\ln 2)/c-1))-3/8\) when considering the \({\varepsilon}^{3}\) error item. Furthermore, we extrapolate the region of the validity of the first-moment method is \(c>2.4094\) by analyzing the higher order error items.

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI
[1] Coppersmith, D.; Gamarnik, D.; Hajiaghayi, M.T.; Sorkin, G.B., Random MAX SAT random MAX CUT, and their phase transitions, Random structures algorithms, 24, 502-545, (2004) · Zbl 1077.68118
[2] Garey, M.R.; Johnson, D.S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. comput. sci., 1, 3, 237-267, (1976) · Zbl 0338.05120
[3] Håstad, J., Some optimal inapproximability results, J. ACM, 48, 4, 798-859, (2001) · Zbl 1127.68405
[4] Aspvall, B.; Plass, M.F.; Tarjan, R.E., A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Inform. process. lett., 8, 3, 121-123, (1979) · Zbl 0398.68042
[5] Bansal, N.; Raman, V., Upper bounds for maxsat: further improved, (), 247-258 · Zbl 0971.68069
[6] Bollobas, B.; Borgs, C.; Chayes, J.T.; Kim, J.H.; Wilson, D.B., The scaling window of the 2-SAT transition, Random structures algorithms, 18, 3, 201-256, (2001) · Zbl 0979.68053
[7] Gramm, J.; Hirsch, E.A.; Niedermeier, R.; Rossmanith, P., Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT, Discrete appl. math., 130, 139-155, (2003) · Zbl 1051.68078
[8] Hirsch, E.A., A new algorithm for MAX-2-SAT, (), 65-73 · Zbl 0959.68047
[9] Hirsch, E.A., New worst-case upper bounds for SAT, J. automat. reason., 24, 4, 397-420, (2000) · Zbl 0960.03009
[10] Niedermeier, R.; Rossmanith, P., New upper bounds for maximum satisfiability, J. algorithms, 36, 63-88, (2000) · Zbl 0959.68049
[11] H. Shen, H. Zhang, An empirical study of MAX-2-SAT phase transitions, in: Proc. of LICS’03 Workshop on Typical Case Complexity and Phase Transitions, Ottawa, CA, June 2003. · Zbl 1179.68148
[12] Achlioptas, D.; Peres, Y., The threshold for random k-SAT is 2klog2−O(k), J. am. math. soc., 17, 4, 947-973, (2004) · Zbl 1093.68075
[13] Xu, K.; Li, W., Exact phase transitions in random constraint satisfaction problems, J. artificial intelligence res., 12, 93-103, (2000) · Zbl 0940.68099
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.