PPAD-membership for problems with exact rational solutions: a general approach via convex optimization

We introduce a general technique for proving membership of search problems with exact rational solutions in PPAD, one of the most well-known classes containing total search problems with polynomial-time verifiable solutions. In particular, we construct a "pseudogate", coined the linear-OPT...

Täydet tiedot

Bibliografiset tiedot
Päätekijät: Filos-Ratsikas, A, Hansen, KA, Høgh, K, Hollender, A
Aineistotyyppi: Conference item
Kieli:English
Julkaistu: Association for Computing Machinery 2024