Document Open Access Logo

Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP

Authors Anton Ehrmanntraut , Fabian Egidy , Christian Glaßer

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.45.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Anton Ehrmanntraut
  • Julius-Maximilians-Universität Würzburg, Germany
Fabian Egidy
  • Julius-Maximilians-Universität Würzburg, Germany
Christian Glaßer
  • Julius-Maximilians-Universität Würzburg, Germany

Cite AsGet BibTex

Anton Ehrmanntraut, Fabian Egidy, and Christian Glaßer. Oracle with P = NP ∩ coNP, but No Many-One Completeness in UP, DisjNP, and DisjCoNP. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.45

Abstract

We construct an oracle relative to which P = NP ∩ coNP, but there are no many-one complete sets in UP, no many-one complete disjoint NP-pairs, and no many-one complete disjoint coNP-pairs. This contributes to a research program initiated by Pudlák [P. Pudlák, 2017], which studies incompleteness in the finite domain and which mentions the construction of such oracles as open problem. The oracle shows that NP ∩ coNP is indispensable in the list of hypotheses studied by Pudlák. Hence one should consider stronger hypotheses, in order to find a universal one.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Oracles and decision trees
  • Theory of computation → Proof complexity
Keywords
  • computational complexity
  • promise classes
  • proof complexity
  • complete sets
  • oracle construction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. O. Beyersdorff. Representable disjoint NP-pairs. In Proceedings 24th International Conference on Foundations of Software Technology and Theoretical Computer Science, volume 3328 of Lecture Notes in Computer Science, pages 122-134. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-30538-5_11.
  2. O. Beyersdorff. Disjoint NP-pairs from propositional proof systems. In Proceedings of Third International Conference on Theory and Applications of Models of Computation, volume 3959 of Lecture Notes in Computer Science, pages 236-247. Springer, 2006. URL: https://doi.org/10.18452/15520.
  3. O. Beyersdorff. Classes of representable disjoint NP-pairs. Theoretical Computer Science, 377(1-3):93-109, 2007. URL: https://doi.org/10.1016/j.tcs.2007.02.005.
  4. O. Beyersdorff. The deduction theorem for strong propositional proof systems. Theory of Computing Systems, 47(1):162-178, 2010. URL: https://doi.org/10.1007/s00224-008-9146-6.
  5. O. Beyersdorff, J. Köbler, and J. Messner. Nondeterministic functions and the existence of optimal proof systems. Theoretical Computer Science, 410(38-40):3839-3855, 2009. URL: https://doi.org/10.1016/j.tcs.2009.05.021.
  6. O. Beyersdorff and Z. Sadowski. Do there exist complete sets for promise classes? Mathematical Logic Quarterly, 57(6):535-550, 2011. URL: https://doi.org/10.1002/malq.201010021.
  7. A. Blass and Y. Gurevich. Equivalence relations, invariants, and normal forms. SIAM Journal on Computing, 13(4):682-689, 1984. URL: https://doi.org/10.1137/0213042.
  8. S. Cook and R. Reckhow. The relative efficiency of propositional proof systems. Journal of Symbolic Logic, 44:36-50, 1979. URL: https://doi.org/10.2307/2273702.
  9. T. Dose. Balance Problems for Integer Circuits and Separations of Relativized Conjectures on Incompleteness in Promise Classes. PhD thesis, Fakultät für Mathematik und Informatik, Universität Würzburg, 2020. URL: https://doi.org/10.25972/OPUS-22220.
  10. T. Dose. Further oracles separating conjectures about incompleteness in the finite domain. Theoretical Computer Science, 847:76-94, 2020. URL: https://doi.org/10.1016/j.tcs.2020.09.040.
  11. T. Dose. An oracle separating conjectures about incompleteness in the finite domain. Theoretical Computer Science, 809:466-481, 2020. URL: https://doi.org/10.1016/j.tcs.2020.01.003.
  12. T. Dose and C. Glaßer. NP-completeness, proof systems, and disjoint NP-pairs. In C. Paul and M. Bläser, editors, 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France, volume 154 of LIPIcs, pages 9:1-9:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.STACS.2020.9.
  13. J. Edmonds. Minimum partition of a matroid into independent subsets. Journal of Research of the National Bureau of Standards, 69B:67-72, 1965. URL: https://doi.org/10.6028/JRES.069B.004.
  14. S. Fenner, L. Fortnow, A. Naik, and J. Rogers. On inverting onto functions. In Proceedings 11th Conference on Computational Complexity, pages 213-223. IEEE Computer Society Press, 1996. Google Scholar
  15. S. A. Fenner, L. Fortnow, A. V. Naik, and J. D. Rogers. Inverting onto functions. Information and Computation, 186(1):90-103, 2003. URL: https://doi.org/10.1016/S0890-5401(03)00119-6.
  16. C. Glaßer, C. Reitwießner, and V. L. Selivanov. The shrinking property for NP and coNP. Theoretical Computer Science, 412(8-10):853-864, 2011. URL: https://doi.org/10.1016/j.tcs.2010.11.035.
  17. C. Glaßer, A. L. Selman, and S. Sengupta. Reductions between disjoint NP-pairs. Information and Computation, 200:247-267, 2005. URL: https://doi.org/10.1016/j.ic.2005.03.003.
  18. C. Glaßer, A. L. Selman, S. Sengupta, and L. Zhang. Disjoint NP-pairs. SIAM Journal on Computing, 33(6):1369-1416, 2004. URL: https://doi.org/10.1137/S0097539703425848.
  19. C. Glaßer, A. L. Selman, and L. Zhang. Canonical disjoint NP-pairs of propositional proof systems. Theoretical Computer Science, 370:60-73, 2007. URL: https://doi.org/10.1007/11549345_35.
  20. C. Glaßer, A. L. Selman, and L. Zhang. The informational content of canonical disjoint NP-pairs. International Journal of Foundations of Computer Science, 20(3):501-522, 2009. URL: https://doi.org/10.1007/978-3-540-73545-8_31.
  21. J. Grollmann and A. L. Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing, 17(2):309-335, 1988. URL: https://doi.org/10.1137/0217018.
  22. J. Hartmanis and L. A. Hemachandra. Complexity classes without machines: On complete languages for UP. Theoretical Computer Science, 58:129-142, 1988. URL: https://doi.org/10.1016/0304-3975(88)90022-9.
  23. Kannan, 1979. Sipser [M. Sipser, 1982] cites an unpublished work by Kannan for asking if there is a set complete for NP ∩ coNP. Google Scholar
  24. E. Khaniki. New relations and separations of conjectures about incompleteness in the finite domain. ArXiv preprint, 2019. URL: http://arxiv.org/abs/1904.01362.
  25. J. Köbler, J. Messner, and J. Torán. Optimal proof systems imply complete sets for promise classes. Information and Computation, 184(1):71-92, 2003. URL: https://doi.org/10.1016/S0890-5401(03)00058-0.
  26. J. Krajícek and P. Pudlák. Propositional proof systems, the consistency of first order theories and the complexity of computations. Journal of Symbolic Logic, 54:1063-1079, 1989. URL: https://doi.org/10.2307/2274765.
  27. N. Megiddo and C. H. Papadimitriou. On total functions, existence theorems and computational complexity. Theoretical Computer Science, 81(2):317-324, 1991. URL: https://doi.org/10.1016/0304-3975(91)90200-L.
  28. J. Messner. On the Simulation Order of Proof Systems. PhD thesis, Universität Ulm, 2000. Google Scholar
  29. C. H. Papadimitriou. On the complexity of integer programming. Journal of the ACM, 28(4):765-768, 1981. URL: https://doi.org/10.1145/322276.322287.
  30. P. Pudlák. On the lengths of proofs of consistency. In Collegium Logicum, pages 65-86. Springer Vienna, 1996. URL: https://doi.org/10.1016/S0049-237X(08)70462-2.
  31. P. Pudlák. On reducibility and symmetry of disjoint NP pairs. Theoretical Computer Science, 295:323-339, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00411-5.
  32. P. Pudlák. On some problems in proof complexity. In O. Beyersdorff, E. A. Hirsch, J. Krajícek, and R. Santhanam, editors, Optimal algorithms and proofs (Dagstuhl Seminar 14421), volume 4, pages 63-63, Dagstuhl, Germany, 2014. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/DagRep.4.10.51.
  33. P. Pudlák. Incompleteness in the finite domain. The Bulletin of Symbolic Logic, 23(4):405-441, 2017. URL: https://doi.org/10.1017/bsl.2017.32.
  34. A. Razborov. On provably disjoint NP-pairs. BRICS Report Series, 36, 1994. URL: https://doi.org/10.7146/brics.v1i36.21607.
  35. A. L. Selman. Promise problems complete for complexity classes. Information and Computation, 78:87-98, 1988. URL: https://doi.org/10.1016/0890-5401(88)90030-2.
  36. M. Sipser. On relativization and the existence of complete sets. In Proceedings 9th ICALP, volume 140 of Lecture Notes in Computer Science, pages 523-531. Springer Verlag, 1982. URL: https://doi.org/10.1007/BFb0012797.
  37. L. G. Valiant. Relative complexity of checking and evaluation. Information Processing Letters, 5:20-23, 1976. URL: https://doi.org/10.1016/0020-0190(76)90097-1.
  38. O. V. Verbitskii. Optimal algorithms for coNP-sets and the EXP=?NEXP problem. Mathematical notes of the Academy of Sciences of the USSR, 50(2):796-801, 1991. URL: https://doi.org/10.1007/BF01157564.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact