Abstract
Phase transition is a dramatic transition from one state to another state when a particular parameter varies. This paper aims to study the phase transition of maximum not-all-equal satisfiability problem (Max NAE SAT), an optimization of not-all-equal satisfiability problem (NAE SAT). Given a conjunctive normal formula (CNF) F with n variables and rn k-clauses (the clause exactly contains k literals), we use first-moment method to obtain an upper bound for f(n, rn) the expectation of the maximum number of NAE-satisfied clauses of random Max NAE k-SAT. In addition, we also consider the phase transition of decision version of random Max NAE k-SAT—bounded not-all-equal satisfiability problem (NAE k-SAT(b)). We demonstrate that there is a phase transition point \(r_{k,b}\) separating the region where almost all NAE k-SAT(b) instances can be solved from the region where almost all NAE k-SAT(b) instances can’t be solved. Furthermore, we analyze the upper bound and lower bound for \(r_{k,b}\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Xu, K., Li, W.: The SAT phase transition. Sci. China Ser. E 42, 494–501 (1999)
Sly, A., Sun, N., Zhang, Y.: The number of solutions for random regular NAE-SAT. In: FOCS (2016)
Larrosa, J., Heras, F., De Givry, S.: A logical approach to efficient Max-SAT solving. Artif. Intell. 172(2–3), 204–233 (2006)
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyansky, L.: Determining computational complexity from characteristic phase transitions. Nature 400, 133–137 (1999)
Kirkpatrick, S., Selman, B.: Critical behavior in the satisfiability of random boolean expressions. Science 264, 1297–1301 (1994)
Xu, K., Li, W.: Exact phase transitions in random constraint satisfaction problems. J. Artif. Intell. Res. 12, 93–103 (2000)
Fan, Y., Shen, J., Xu, K.: A general model and thresholds for random constraint satisfaction problems original. Artif. Intell. 193, 1–17 (2012)
Gent, I.P., Walsh, T.: The TSP phase transition. Artif. Intell. 88(1–2), 349–358 (1996)
Walsh, T.: Where are the really hard manipulation problems? the phase transition in manipulating the veto rule. In: Proceedings of the 21st International Jont Conference on Artifical intelligence, Morgan Kaufmann Publishers Inc. (2009)
Huang, P., Yin, M.: An upper (lower) bound for Max (Min) CSP. Sci. China Inf. Sci. 57(7), 1–9 (2014)
Gao, J., Wang, J., Yin, M.: Experimental analyses on phase transitions in compiling satisfiability problems. Sci. China Inf. Sci. 58, 1–11 (2015)
Zhou, J., Yin, M., Li, X., Wang, J.: Phase transitions of EXPSPACE-complete problems: a further step. Int. J. Found. Comput. Sci. 23(01), 173–184 (2012)
Achlioptas, D., Chtcherba, A., Istrate, G., Moore, C.: The phase transition in 1-in-k SAT and NAE 3-SAT. In: SODA, pp. 721–722 (2001)
Achlioptas, D.: The asymptotic order of the random k-SAT threshold. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS02), pp. 779–788 (2002)
Coja-Oglan, A., Panagiotou, K.: Catching the k-NAE SAT threshold. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 899–908 (May 2012)
Ding, J., Sly, A., Sun, N.: Satisfiability threshold for random regular NAE-SAT. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pp. 814–822 (May 2014)
Achlioptas, D., Naor, A., Peres, Y.: Rigorous location of phase transitions in hard optimization problems. Nature 435, 759–764 (2005)
Coppersmith, D., et al.: Random MAX SAT, random MAX CUT, and their phase transitions. Random Struct. Algorithms 24, 502–545 (2004)
Xu, X.L., Gao, Z.S., Xu, K.: A tighter upper bound for random MAX 2-SAT. Inf. Process. Lett. 111, 115–119 (2011)
Zhang, W.: Phase transitions and backbones of 3-SAT and maximum 3-SAT. In: Walsh, T. (ed.) CP 2001. LNCS, vol. 2239, pp. 153–167. Springer, Heidelberg (2001). doi:10.1007/3-540-45578-7_11
Bailey, D.D., Kolaitis, P.G.: Phase transitions of bounded satisfiability problems. In: IJCAI, pp. 1187–1193 (2003)
Acknowledgement
The authors of this paper wish to extend their sincere gratitude to all anonymous reviewers for their efforts. This work was supported in part by NSFC (under Grant Nos.61503074, 61403076, 61402070, and 61403077), the Natural Science Foundation for Youths of JiLin Province (20160520104JH) and (NCET-13-0724).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Zhou, J., Hu, S., Zou, T., Yin, M. (2017). Phase Transition for Maximum Not-All-Equal Satisfiability. In: Xiao, M., Rosamond, F. (eds) Frontiers in Algorithmics. FAW 2017. Lecture Notes in Computer Science(), vol 10336. Springer, Cham. https://doi.org/10.1007/978-3-319-59605-1_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-59605-1_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-59604-4
Online ISBN: 978-3-319-59605-1
eBook Packages: Computer ScienceComputer Science (R0)