Document Open Access Logo

The Robustness of LWPP and WPP, with an Application to Graph Reconstruction

Authors Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, Osamu Watanabe

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.51.pdf
  • Filesize: 418 kB
  • 14 pages

Document Identifiers

Author Details

Edith Hemaspaandra
  • Rochester Institute of Technology, Rochester, NY, USA
Lane A. Hemaspaandra
  • University of Rochester, Rochester, NY, USA
Holger Spakowski
  • University of Cape Town, Rondebosch, South Africa
Osamu Watanabe
  • Tokyo Institute of Technology, Tokyo, Japan

Cite As Get BibTex

Edith Hemaspaandra, Lane A. Hemaspaandra, Holger Spakowski, and Osamu Watanabe. The Robustness of LWPP and WPP, with an Application to Graph Reconstruction. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.51

Abstract

We show that the counting class LWPP [S. Fenner et al., 1994] remains unchanged even if one allows a polynomial number of gap values rather than one. On the other hand, we show that it is impossible to improve this from polynomially many gap values to a superpolynomial number of gap values by relativizable proof techniques.
The first of these results implies that the Legitimate Deck Problem (from the study of graph reconstruction) is in LWPP (and thus low for PP, i.e., PP^{Legitimate Deck} = PP) if the weakened version of the Reconstruction Conjecture holds in which the number of nonisomorphic preimages is assumed merely to be polynomially bounded. This strengthens the 1992 result of Köbler, Schöning, and Torán [J. Köbler et al., 1992] that the Legitimate Deck Problem is in LWPP if the Reconstruction Conjecture holds, and provides strengthened evidence that the Legitimate Deck Problem is not NP-hard.
We additionally show on the one hand that our main LWPP robustness result also holds for WPP, and also holds even when one allows both the rejection- and acceptance- gap-value targets to simultaneously be polynomial-sized lists; yet on the other hand, we show that for the #P-based analog of LWPP the behavior much differs in that, in some relativized worlds, even two target values already yield a richer class than one value does.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • structural complexity theory
  • robustness of counting classes
  • the legitimate deck problem
  • PP-lowness
  • the Reconstruction Conjecture

Metrics

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

Related Versions

References

  1. J. Bondy. A graph reconstructor’s manual. In Surveys in Combinatorics, London Mathematical Society Lecture Notes Series 66, pages 221-252. Cambridge University Press, 1991. Google Scholar
  2. J. Bondy and R. Hemminger. Graph reconstruction - a survey. Journal of Graph Theory, 1:227-268, 1977. Google Scholar
  3. D. Bovet, P. Crescenzi, and R. Silvestri. A uniform approach to define complexity classes. Theoretical Computer Science, 104(2):263-283, 1992. Google Scholar
  4. J. Cai, T. Gundermann, J. Hartmanis, L. Hemachandra, V. Sewelson, K. Wagner, and G. Wechsung. The boolean hierarchy II: Applications. SIAM Journal on Computing, 18(1):95-111, 1989. Google Scholar
  5. J. Cox and T. Pay. An overview of some semantic and syntactic complexity classes. Technical Report arXiv:1806.03501 [cs.CC], ArXiv.org, June 2018. Google Scholar
  6. M. de Graaf and P. Valiant. Comparing EQP and MOD_p^kP using polynomial degree lower bounds. Technical Report quant-ph/0211179, Quantum Physics, 2002. Google Scholar
  7. The Editors (of the Journal of Graph Theory). Editorial note. Journal of Graph Theory, 1(3), 1977. Google Scholar
  8. S. Fenner, L. Fortnow, and S. Kurtz. Gap-definable counting classes. Journal of Computer and System Sciences, 48(1):116-148, 1994. Google Scholar
  9. M. Furst, J. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17:13-27, 1984. Google Scholar
  10. J. Håstad. Computational Limitations of Small-Depth Circuits. MIT Press, 1987. Google Scholar
  11. E. Hemaspaandra, L. Hemaspaandra, S. Radziszowski, and R. Tripathi. Complexity results in graph reconstruction. Discrete Applied Mathematics, 155(2):103-118, 2007. Google Scholar
  12. E. Hemaspaandra, L. Hemaspaandra, H. Spakowski, and O. Watanabe. The robustness of LWPP and WPP, with an application to graph reconstruction. Technical Report arXiv:1711.01250v2 [cs.CC], ArXiv.org, November 2017. Revised, April 2018. Google Scholar
  13. P. Kelly. On Isometric Transformations. PhD thesis, University of Wisconsin, USA, 1942. Google Scholar
  14. K. Ko. Relativized polynomial-time hierarchies having exactly k levels. SIAM Journal on Computing, 18(2):392-408, 1989. Google Scholar
  15. J. Köbler, U. Schöning, and J. Torán. Graph isomorphism is low for PP. Computational Complexity, 2:301-330, 1992. Google Scholar
  16. D. Kratsch and L. Hemachandra. On the complexity of graph reconstruction. In Proceedings of the 8th Conference on Fundamentals of Computation Theory, pages 318-328. Springer-Verlag Lecture Notes in Computer Science #529, 1991. Google Scholar
  17. D. Kratsch and L. Hemaspaandra. On the complexity of graph reconstruction. Mathematical Systems Theory, 27(3):257-273, 1994. Google Scholar
  18. J. Lauri and R. Scapellato. Topics in Graph Automorphisms and Reconstruction. Cambridge University Press, 2003. Google Scholar
  19. T. Long. Strong nondeterministic polynomial-time reducibilities. Theoretical Computer Science, 21:1-25, 1982. Google Scholar
  20. A. Mansfield. The relationship between the computational complexities of the legitimate deck and isomorphism problems. Quart. J. Math. Ser., 33(2):345-347, 1982. Google Scholar
  21. B. Manvel. Reconstruction of graphs: Progress and prospects. Congressus Numerantium, 63:177-187, 1988. Google Scholar
  22. C. St. J. A. Nash-Williams. The reconstruction problem. In L. Beineke and R. Wilson, editors, Selected Topics in Graph Theory, pages 205-236. Academic Press, 1978. Google Scholar
  23. M. Ogiwara and L. Hemachandra. A complexity theory for feasible closure properties. Journal of Computer and System Sciences, 46(3):295-325, 1993. Google Scholar
  24. U. Schöning. A low and a high hierarchy within NP. Journal of Computer and System Sciences, 27:14-28, 1983. Google Scholar
  25. J. Simon. On Some Central Problems in Computational Complexity. PhD thesis, Cornell University, Ithaca, N.Y., 1975. Available as Cornell Department of Computer Science Technical Report TR75-224. Google Scholar
  26. H. Spakowski, M. Thakur, and R. Tripathi. Quantum and classical complexity classes: Separations, collapses, and closure properties. Information and Computation, 200(1):1-34, 2005. Google Scholar
  27. L. Stockmeyer and A. Meyer. Word problems requiring exponential time. In Proceedings of the 5th ACM Symposium on Theory of Computing, pages 1-9. ACM Press, 1973. Google Scholar
  28. S. Ulam. A Collection of Mathematical Problems. Interscience Publishers, New York, 1960. Google Scholar
  29. K. Wagner. The complexity of combinatorial problems with succinct input representations. Acta Informatica, 23(3):325-356, 1986. Google Scholar
  30. C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3:23-33, 1977. Google Scholar
  31. A. Yao. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, pages 1-10, 1985. Google Scholar
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 About DROPS Imprint Privacy Contact