An oracle separating conjectures about incompleteness in the finite domain

Theoretical Computer Science - Tập 809 - Trang 466-481 - 2020
Titus Dose1
1Julius-Maximilians-Universität Würzburg, Germany

Tài liệu tham khảo

Beyersdorff, 2009, Nondeterministic functions and the existence of optimal proof systems, Theor. Comput. Sci., 410, 3839, 10.1016/j.tcs.2009.05.021 Cook, 1979, The relative efficiency of propositional proof systems, J. Symb. Log., 44, 36, 10.2307/2273702 Dose, 2019 Dose Dose Even, 1984, The complexity of promise problems with applications to public-key cryptography, Inf. Control, 61, 159, 10.1016/S0019-9958(84)80056-X Even, 1980, Cryptocomplexity and NP-completeness, vol. 85, 195 Grollmann, 1988, Complexity measures for public-key cryptosystems, SIAM J. Comput., 17, 309, 10.1137/0217018 Glaßer, 2004, Disjoint NP-pairs, SIAM J. Comput., 33, 1369, 10.1137/S0097539703425848 Hartmanis, 1988, Complexity classes without machines: on complete languages for UP, Theor. Comput. Sci., 58, 129, 10.1016/0304-3975(88)90022-9 Khaniki Köbler, 2000, Is the standard proof system for sat p-optimal?, 361 Köbler, 2003, Optimal proof systems imply complete sets for promise classes, Inf. Comput., 184, 71, 10.1016/S0890-5401(03)00058-0 Krajíček, 1989, Propositional proof systems, the consistency of first order theories and the complexity of computations, J. Symb. Log., 54, 1063, 10.2307/2274765 Megiddo, 1991, On total functions, existence theorems and computational complexity, Theor. Comput. Sci., 81, 317, 10.1016/0304-3975(91)90200-L Papadimitriou, 1994 Pudlák, 1996, On the lengths of proofs of consistency, 65, 10.1007/978-3-7091-9461-4_5 Pudlák, 2013, Logical Foundations of Mathematics and Computational Complexity - A Gentle Introduction Pudlák, 2017, Incompleteness in the finite domain, Bull. Symb. Log., 23, 405, 10.1017/bsl.2017.32 Razborov, 1994, On provably disjoint NP-pairs, Electron. Colloq. Comput. Complex., 1