LIPIcs.MFCS.2016.12.pdf
- Filesize: 0.53 MB
- 14 pages
Document
On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems
Authors
-
Part of:
Volume:
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-19
Cite As Get BibTex
Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang. On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.12
Abstract
What is the minimum amount of information and time needed to solve 2SAT? When the instance is known, it can be solved in polynomial time, but is this also possible without knowing the instance? Bei, Chen and Zhang (STOC'13) considered a model where the input is accessed by proposing possible assignments to a special oracle. This oracle, on encountering some constraint unsatisfied by the proposal, returns only the constraint index. It turns out that, in this model, even 1SAT cannot be solved in polynomial time unless P=NP. Hence, we consider a model in which the input is accessed by proposing probability distributions over assignments to the variables. The oracle then returns the index of the constraint that is most likely to be violated by this distribution. We show that the information obtained this way is sufficient to solve 1SAT in polynomial time, even when the clauses can be repeated. For 2SAT, as long as there are no repeated clauses, in polynomial time we can even learn an equivalent formula for the hidden instance and hence also solve it. Furthermore, we extend these results to the quantum regime. We show that in this setting 1QSAT can be solved in polynomial time up to constant precision, and 2QSAT can be learnt in polynomial time up to inverse polynomial precision.
Subject Classification
Keywords
- computational complexity
- satisfiability problems
- trial and error
- quantum computing
- learning theory
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Daniel S. Abrams and Seth Lloyd. Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems. Phys. Rev. Lett., 81:3992-3995, 1998.
- Itai Arad, Miklos Santha, Aarthi Sundaram, and Shengyu Zhang. Linear time algorithm for quantum 2SAT. CoRR, abs/1508.06340, 2015. To appear in the 43rd International Colloquium on Automata, Languages and Programming. URL: http://arxiv.org/abs/1508.06340.
-
Bengt Aspvall, Michael F. Plass, and Robert Endre Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8(3):121-123, 1979. Erratum: Information Processing Letters 14(4): 195 (1982).
- Xiaohui Bei, Ning Chen, and Shengyu Zhang. On the complexity of trial and error. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, STOC, pages 31-40. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488613.
- Xiaohui Bei, Ning Chen, and Shengyu Zhang. Solving linear programming with constraints unknown. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, ICALP (1), volume 9134 of Lecture Notes in Computer Science, pages 129-142. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47672-7_11.
- Sergey Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. In Kazem Mahdavi, Deborah Koslover, and Leonard L. Brown, editors, Contemporary Mathematics, volume 536. American Mathematical Society, 2011. URL: http://arxiv.org/abs/quant-ph/0602108.
-
S. A. Cook. The complexity of theorem proving procedures. In Proceedings of the Third Annual ACM Symposium, pages 151-158, New York, 1971. ACM.
- Niel de Beaudrap and Sevag Gharibian. A linear time algorithm for quantum 2-SAT. CoRR, abs/1508.07338, 2015. To appear in 31st Conference on Computational Complexity. URL: http://arxiv.org/abs/1508.07338.
-
Shimon Even, Alon Itai, and Adi Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691-703, 1976.
- David Gosset and Daniel Nagaj. Quantum 3-SAT is QMA1-complete. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 0:756-765, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.86.
- Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, and Aarthi Sundaram. On the complexity of trial and error for constraint satisfaction problems. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, ICALP, volume 8572 of Lecture Notes in Computer Science, pages 663-675. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_55.
- M. R. Krom. The decision problem for a class of first-order formulas in which all disjunctions are binary. Mathematical Logic Quarterly, 13(1-2):15-20, 1967. URL: http://dx.doi.org/10.1002/malq.19670130104.
-
L. A. Levin. Universal sequential search problems. Problems of Information Transmission, 9(3):265-266, 1973.
-
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.