2-D Tucker is PPA complete
type: Item
instance of: scholarly article
title: 2-D Tucker is PPA complete
zbMATH Open document ID: 1436.68127
author: James Aisenberg
author: Maria Luisa Bonet
author: Samuel R. Buss
published in: Journal of Computer and System Sciences
publication date: 2019-11-29T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68U05
zbMATH DE Number: 7138706
zbMATH Keywords: Tucker lemma
zbMATH Keywords: NP search problems
zbMATH Keywords: parity principle
zbMATH Keywords: PPA
zbMATH Keywords: TFNP
MaRDI profile type: Publication
full work available at URL: j.jcss.2019.09.002
OpenAlex ID: W2976501052
cites work: Short proofs of the Kneser-Lovász coloring principle
cites work: The relative complexity of NP search problems
cites work: Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
cites work: On the Complexity of 2D Discrete Fixed Point Problem
cites work: On the complexity of 2D discrete fixed point problem
cites work: Settling the complexity of computing two-player Nash equilibria
cites work: The complexity of computing a Nash equilibrium
cites work: Understanding PPA-completeness
cites work: Consensus halving is PPA-complete
cites work: Variable Dimension Complexes Part I: Basic Theory
cites work: Variable Dimension Complexes Part II: A Unified Approach to Some Combinatorial Lemmas in Topology
cites work: A constructive proof of Tucker's combinatorial lemma
cites work: Locally 2-Dimensional Sperner Problems Complete for the Polynomial Parity Argument Classes
cites work: A Sperner lemma complete for PPA
cites work: Integer factoring and modular square roots
cites work: A combinatorical proof of Kneser's conjecture
cites work: Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in cooperation with Anders Björner and Günter M. Ziegler
cites work: On the complexity of the parity argument and other inefficient proofs of existence
cites work: Hamiltonian Cycles and Uniquely Edge Colourable Graphs
cites work: Generalized Kneser coloring theorems with combinatorial proofs
Wikidata QID: Q127200367
DOI: 10.1016/J.JCSS.2019.09.002
Recommended article: Complete solution to the TP2completion problem
Recommended article: Understanding PPA-completeness
Recommended article: Q3129188
Recommended article: A further improvement on approximating TTP-2
Recommended article: Consensus halving is PPA-complete
Recommended article: Q4385405
Recommended article: Projection 2 Goes Turbulent - and Fully Implicit
description: scientific article; zbMATH DE number 7138706