2-D Tucker is PPA complete

摘要

The 2-D Tucker search problem is shown to be PPA-hard under many-one reductions; therefore it is complete for PPA. The same holds for k -D Tucker for all k 2 . This corrects a claim in the literature that the Tucker search problem is in PPAD.