Publication
2D-TUCKER Is PPAD-Complete
2009
Article de conférence
Article de conférence
Résumé
Tucker's lemma states that if we triangulate the unit disc centered at the origin and color the vertices with {1, 1,2, 2} in an antipodal way (if vertical bar z vertical bar = 1, then the sum of the colors of z and -z is zero), then there must be an edge For which the sum of the colors of its endpoints is zero. But how hard is it to find such all edge? We show Butt if the triangulation is exponentially large and the coloring is determined by a deterministic Turing-machine, then this problem is PPAD-complete which implies that there is not too much hope for a polynomial algorithm.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.