An oracle separating conjectures about incompleteness in the finite domain
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