2019/04/02 by Erfan Khaniki, Khaniki, Erfan · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.1904.01362
openalex publication_date 2019/04/02 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
Our main results are in the following three sections:\n 1. We prove new relations between proof complexity conjectures that are\ndiscussed in citepu18.\n 2. We investigate the existence of p-optimal proof systems for\n\TAUT, assuming the collapse of cal C and sf N cal C (the\nnondeterministic version of cal C) for some new classes cal C and also\nprove new conditional independence results for strong theories, assuming\nnonexistence of p-optimal proof systems.\n 3. We construct two new oracles cal V and cal W. These two oracles\nimply several new separations of proof complexity conjectures in relativized\nworlds. Among them, we prove that existence of a p-optimal proof system for\n\TAUT and existence of a complete problem for \TFNP are\nindependent of each other in relativized worlds which was not known before.\n