Abstract
The XSAT problem asks for solutions of a set of clauses where for every clause exactly one literal is satisfied. The present work investigates a variant of this well-investigated topic where variables can take a joker-value (which is preserved by negation) and a clause is satisfied iff either exactly one literal is true and no literal has a joker value or exactly one literal has a joker value and no literal is true. While JX2SAT is in polynomial time, the problem becomes NP-hard when one searches for a solution with the minimum number of jokers used and the decision problem X3SAT can be reduced to the decision problem of the JX2SAT problem with a bound on the number of jokers used. JX3SAT is in both cases, with or without optimisation of the number of jokers, NP-hard and X3SAT can be reduced to it without increasing the number of variables. Furthermore, the general JXSAT problem can be solved in the same amount of time as variable-weighted XSAT and the obtained solution has the minimum amount of number of jokers possible.
S. Jain was supported in part by NUS grant C252-000-087-001; furthermore, S. Jain and F. Stephan have been supported in part by the Singapore Ministry of Education Academic Research Fund Tier 2 grant MOE2016-T2-1-019/R146-000-234-112. Part of the work was done while S. Schwarz was on sabbatical leave to the National University of Singapore.
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
Accorsi, R.: MAX2SAT is NP-complete. WINS-ILLC, University of Amsterdam (1999)
Chen, H.: A rendezvous of logic, complexity, and algebra. SIGACT News (Logic Column). ACM (2006)
Gaspers, S., Sorkin, G.B.: Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets. ACM Trans. Algorithms (TALG) 13(4), 44:1–44:36 (2017)
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of Computer Computations, pp. 85–103. Springer, Boston (1972). https://doi.org/10.1007/978-1-4684-2001-2_9
Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, pp. 11–17. ACM (2006)
Lardeux, F., Saubion, F., Hao, J.-K.: Three truth values for the SAT and MAX-SAT problems. In: International Joint Conference on Artificial Intelligence, IJCAI 2005, vol. 19, p. 187. Lawrence Erlbaum Associates Ltd. (2005)
Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. J. Algorithms 36, 63–88 (2000)
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)
Porschen, S.: On variable-weighted exact satisfiability problems. Ann. Math. Artif. Intell. 51(1), 27–54 (2007)
Porschen, S., Plagge, G.: Minimizing variable-weighted X3SAT. In: Proceedings of the International Multiconference of Engineers and Computer Scientists, IMECS 2010, Hongkong, 17–19 March 2010, vol. 1, pp. 449–454 (2010)
Porschen, S., Schmidt, T.: On some SAT-variants over linear formulas. In: Nielsen, M., Kučera, A., Miltersen, P.B., Palamidessi, C., Tůma, P., Valencia, F. (eds.) SOFSEM 2009. LNCS, vol. 5404, pp. 449–460. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-540-95891-8_41
Raible, D., Fernau, H.: A new upper bound for max-2-SAT: a graph-theoretic approach. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 551–562. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85238-4_45
Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 216–226 (1978)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Hoi, G., Jain, S., Schwarz, S., Stephan, F. (2019). Exact Satisfiabitity with Jokers. In: Gopal, T., Watada, J. (eds) Theory and Applications of Models of Computation. TAMC 2019. Lecture Notes in Computer Science(), vol 11436. Springer, Cham. https://doi.org/10.1007/978-3-030-14812-6_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-14812-6_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-14811-9
Online ISBN: 978-3-030-14812-6
eBook Packages: Computer ScienceComputer Science (R0)