Complete Disjoint CoNP-Pairs but No Complete Total Polynomial Search Problems Relative to an Oracle

摘要

Consider the following conjectures:1. TFNP: the set TFNP of all total polynomial search problems has no complete problems with respect to polynomial reductions.2. DisjCoNP: there exists no many-one complete disjoint coNP-pair. We construct an oracle relative to which TFNP holds and DisjCoNP does not hold. This partially answers a question by Pudlak [12], who lists several conjectures and asks for oracles that show corresponding relativized conjectures to be different. As there exists a relativizable proof for the implication DisjCoNP ⇒ TFNP [12], relative to our oracle the conjecture TFNP is strictly stronger than DisjCoNP.