Abstract
This paper is concerned with the design and analysis of a random walk algorithm for the 2CNF implication problem (2CNFI). In 2CNFI, we are given two 2CNF formulas \({\phi_{1}}\) and \({\phi_{2}}\) and the goal is to determine whether every assignment that satisfies \({\phi_{1}}\) , also satisfies \({\phi_{2}}\) . The implication problem is clearly coNP-complete for instances of kCNF, k ≥ 3; however, it can be solved in polynomial time, when k ≤ 2. The goal of this paper is to provide a Monte Carlo algorithm for 2CNFI with a bounded probability of error. The technique developed for 2CNFI is then extended to derive a randomized, polynomial time algorithm for the problem of checking whether a given 2CNF formula Nae-implies another 2CNF formula.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Karger D.R., Klein P.N., Tarjan R.E.: A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42(2), 321–328 (1995)
Motwani R., Raghavan P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)
Papadimitriou, C.H.: On selecting a satisfying truth assignment. In: IEEE, editor, Proceedings: 32nd annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1–4, 1991, pp. 163–169, 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA, 1991. IEEE Computer Society Press
Papadimitriou C.H.: Computational Complexity. Addison-Wesley, New York (1994)
Ross S.M.: Probability Models, 7th edn. Academic Press, Inc., London (2000)
Schöning, U.: New algorithms for k-SAT based on the local search principle. In: MFCS: Symposium on Mathematical Foundations of Computer Science (2001)
Subramani, K., Gu, X.: Absorbing random walks and the nae2sat problem. Fundamenta Informatica. (2008, Submitted)
Subramani K.: Cascading random walks. Int. J. Found. Comput. Sci. (IJFCS) 16(3), 599–622 (2005)
Subramani K. et al.: Absorbing random walks and the nae2sat problem. In: Preparata, F. et al. (eds) Proceedings of the 2nd Annual International Frontiers of Algorithmics Workshop. Lecture Notes in Computer Science, vol. 5059, pp. 89–100. Springer, Heidelberg (2008)
Valiant L.G.: A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984)
Wei, W., Selman, B.: Accelerating random walks. In: The Eighth International Conference on Constraint Programming (CP), LNCS, pp. 216–232 (2002)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research has been supported in part by the Air Force Office of Scientific Research under grant FA9550-06-1-0050.
Rights and permissions
About this article
Cite this article
Subramani, K., Lai, HJ. & Gu, X. Random walks for selected boolean implication and equivalence problems. Acta Informatica 46, 155–168 (2009). https://doi.org/10.1007/s00236-009-0089-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00236-009-0089-4