Document Open Access Logo

Understanding PPA-Completeness

Authors Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu

PDF
Thumbnail PDF

File

LIPIcs.CCC.2016.23.pdf
  • Filesize: 0.88 MB
  • 25 pages

Document Identifiers

Author Details

Xiaotie Deng
Jack R. Edmonds
Zhe Feng
Zhengyang Liu
Qi Qi
Zeying Xu

Cite AsGet BibTex

Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, and Zeying Xu. Understanding PPA-Completeness. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 23:1-23:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.CCC.2016.23

Abstract

We consider the problem of finding a fully colored base triangle on the 2-dimensional Möbius band under the standard boundary condition, proving it to be PPA-complete. The proof is based on a construction for the DPZP problem, that of finding a zero point under a discrete version of continuity condition. It further derives PPA-completeness for versions on the Möbius band of other related discrete fixed point type problems, and a special version of the Tucker problem, finding an edge such that if the value of one end vertex is x, the other is -x, given a special anti-symmetry boundary condition. More generally, this applies to other non-orientable spaces, including the projective plane and the Klein bottle. However, since those models have a closed boundary, we rely on a version of the PPA that states it as to find another fixed point giving a fixed point. This model also makes it presentationally simple for an extension to a high dimensional discrete fixed point problem on a non-orientable (nearly) hyper-grid with a constant side length.
Keywords
  • Fixed Point Computation
  • PPA-Completeness

Metrics

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

References

  1. James Aisenberg, Maria Luisa Bonet, and Sam Buss. 2-D Tucker is PPA complete. ECCC TR15-163, 2015. Google Scholar
  2. Noga Alon. Combinatorial nullstellensatz. Combinatorics, Probability and Computing, 8, 1999. Google Scholar
  3. Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. The relative complexity of NP search problems. Journal of Computer and System Sciences, 57(1):3-19, 1998. URL: http://dx.doi.org/10.1006/jcss.1998.1575.
  4. Kathie Cameron. Thomason’s algorithm for finding a second hamiltonian circuit through a given edge in a cubic graph is exponential on krawczyk’s graphs. Discrete Mathematics, 235(1-3):69-77, 2001. Chech and Slovak 3. URL: http://dx.doi.org/10.1016/S0012-365X(00)00260-0.
  5. Kathie Cameron and Jack Edmonds. Some graphic uses of an even number of odd nodes. Annales de l'institut Fourier, 49(3):815-827, 1999. URL: http://eudml.org/doc/75365.
  6. Chih-Wei Chang, Ming Liu, Sunghyun Nam, Shuang Zhang, Yongmin Liu, Guy Bartal, and Xiang Zhang. Optical möbius symmetry in metamaterials. Phys. Rev. Lett., 105:235501, Dec 2010. URL: http://dx.doi.org/10.1103/PhysRevLett.105.235501.
  7. Xi Chen and Xiaotie Deng. On the complexity of 2D discrete fixed point problem. In In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Lecture Notes in Computer Science, pages 489-500. Springer-Verlag, 2006. Google Scholar
  8. Xi Chen and Xiaotie Deng. Matching algorithmic bounds for finding a brouwer fixed point. JACM, 55(3), 2008. Google Scholar
  9. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3):14:1-14:57, May 2009. URL: http://dx.doi.org/10.1145/1516512.1516516.
  10. C. Chevalley. Démonstration d'une hypothèse de m. artin. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 11(1):73-75, 1935. URL: http://dx.doi.org/10.1007/BF02940714.
  11. Xiaotie Deng, Qi Qi, Amin Saberi, and Jie Zhang. Discrete fixed points: Models, complexities, and applications. Mathematics of Operations Research, 36(4):636-652, 2011. URL: http://dx.doi.org/10.1287/moor.1110.0511.
  12. Jack Edmonds and Laura Sanità. On finding another room-partitioning of the vertices. Electronic Notes in Discrete Mathematics, 36:1257-1264, 2010. URL: http://dx.doi.org/10.1016/j.endm.2010.05.159.
  13. M. C. Escher. Möbius strip ii (red ants). http://www.mcescher.com/Gallery/recogn-bmp/LW441.jpg, 1963. [Online; accessed 3-March-2016].
  14. Y. N. Fang, Yao Shen, Qing Ai, and C. P. Sun. Negative Refraction Induced by Möbius Topology. ArXiv e-prints, January 2015. URL: http://arxiv.org/abs/1501.05729.
  15. Katalin Friedl, Gábor Ivanyos, Miklos Santha, and Yves F. Verhoeven. Locally 2-dimensional sperner problems complete for the polynomial parity argument classes. submitted. In In Proceedings of the 6th Italian Conference on Algorithms and Complexity. Lecture Notes in Computer Science, pages 380-391. Springer-Verlag, 2006. Google Scholar
  16. Paul Goldberg. The complexity of the path-following solutions of two-dimensional sperner/brouwer functions. arXiv:1506.04882 [cs.CC], 2015. Google Scholar
  17. Michelangelo Grigni. A sperner lemma complete for PPA. Information Processing Letters, 77(5-6):255-259, 2001. URL: http://dx.doi.org/10.1016/S0020-0190(00)00152-6.
  18. Dongran Han, Suchetan Pal, Yan Liu, and Hao Yan. Folding and cutting dna into reconfigurable topological nanostructures. Nat Nano, 5(10):712-717, 10 2010. URL: http://dx.doi.org/10.1038/nnano.2010.193.
  19. Michael D Hirsch, Christos H Papadimitriou, and Stephen A Vavasis. Exponential lower bounds for finding brouwer fix points. Journal of Complexity, 5(4):379-416, 1989. URL: http://dx.doi.org/10.1016/0885-064X(89)90017-4.
  20. Takuya Iimura. A discrete fixed point theorem and its applications. Journal of Mathematical Economics, 39(7):725-742, 2003. URL: http://dx.doi.org/10.1016/S0304-4068(03)00007-7.
  21. Emil Jerábek. Integer factoring and modular square roots. CoRR, abs/1207.5220, 2012. URL: http://arxiv.org/abs/1207.5220.
  22. Shiva Kintali. A compendium of PPAD-complete problems. http://www.cs.princeton.edu/~kintali/ppad.html. [Online; accessed 3-March-2016].
  23. Adam Krawczyk. The complexity of finding a second hamiltonian cycle in cubic graphs. Journal of Computer and System Sciences, 58(3):641-647, 1999. URL: http://dx.doi.org/10.1006/jcss.1998.1611.
  24. O. L. Mangasarian. Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(4):778-780, 1964. URL: http://www.jstor.org/stable/2946349.
  25. Ruta Mehta. Constant rank bimatrix games are ppad-hard. In Proceedings of the Fourty-Sixth Annual ACM Symposium on Theory of Computing, STOC'14, pages 545-554, New York, NY, USA, 2014. ACM. Google Scholar
  26. Dömötör Pálvölgyi. 2d-tucker is ppad-complete. In 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings, pages 569-574. Springer-Verlag, 2009. Google Scholar
  27. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80063-7.
  28. Rahul Savani and Bernhard von Stengel. Hard-to-solve bimatrix games. Econometrica, 74(2):397-429, 2006. URL: http://dx.doi.org/10.1111/j.1468-0262.2006.00667.x.
  29. Herbert E. Scarf. The approximation of fixed points of a continuous mapping. Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University, 1967. URL: http://EconPapers.repec.org/RePEc:cwl:cwldpp:216r.
  30. A.G. Thomason. Hamiltonian cycles and uniquely edge colourable graphs. In B. Bollobás, editor, Advances in Graph Theory, volume 3 of Annals of Discrete Mathematics, pages 259-268. Elsevier, 1978. URL: http://dx.doi.org/10.1016/S0167-5060(08)70511-9.
  31. Michael J Todd. The computation of fixed points and applications, volume 124. Springer Science &Business Media, 2013. Google Scholar
  32. Eric W. Weisstein. Klein bottle. http://mathworld.wolfram.com/KleinBottle.html. [Online; accessed 3-March-2016].
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