TFNP
summary
Claims that relate TFNP subclasses to concrete models: resolution = PLS via an explicit reduction from search(F) to the sink-of-DAG problem (one DAG vertex per clause, output decision trees query clause variables), and the converse uses a delayer–prover strategy to extract a small resolution from a decision-tree reduction. Key tools are decision‑tree and communication lifting, a complexity measure log(size)+width, and a canonical proof system built from the reflection principle; necessary conditions are closure under decision‑tree reductions and polylog verifiable proofs of soundness.
AI-written summary · about