An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem

Marco Aldi, Sevag Gharibian, Dorian Rudolph

The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intract…