2019/04/11 by Dose, Titus
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.1904.06175
Pudlák [Pud17] lists several major conjectures from the field of proof complexity and asks for oracles that separate corresponding relativized conjectures. Among these conjectures are: - DisjNP: The class of all disjoint NP-pairs does not have many-one complete elements. - SAT: NP does not contain many-one complete sets that have P-optimal proof systems. - UP: UP does not have many-one complete problems. - NP\capcoNP: NP\capcoNP does not have many-one complete problems. As one answer to this question, we construct an oracle relative to which DisjNP, ¬ SAT, UP, and NP\capcoNP hold, i.e., there is no relativizable proof for the implication DisjNP\wedge UP\wedge NP\capcoNP\RightarrowSAT. In particular, regarding the conjectures by Pudlák this extends a result by Khaniki [Kha19].