Understanding PPA-completeness

DOI10.4230/LIPICS.CCC.2016.23MaRDI QIDQ5368757zbMATH OpenOpenAlexFDO

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

Publication date 10 October 2017

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.CCC.2016.23

zbMATH Keywords

fixed-point computationPPA-completeness

Mathematics Subject Classification ID

Relations of low-dimensional topology with graph theory (57M15) Triangulating manifolds (57Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Understanding PPA-completeness
• Minimality and completions of PA
• Computing and Combinatorics
• scientific article; zbMATH DE number 7768354
• Completeness in PVS of a nominal unification algorithm
• Modularity of completeness revisited
• scientific article; zbMATH DE number 1868899
• On completeness
• Completion by perturbations
• Completeness of resolution revisited

Cited in

(6)

• 2-D Tucker is PPA complete
• A PPA parity theorem about trees in a bipartite graph
• Understanding PPA-completeness
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• Computing exact solutions of consensus halving and the Borsuk-Ulam theorem
• scientific article; zbMATH DE number 7561747 (Why is no real title available?)

This page was built for publication: Understanding PPA-completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368757)