On Optimal Heuristic Randomized Semidecision Procedures, with Applications to Proof Complexity and Cryptography

被引：0
作者：
Edward A. Hirsch
Dmitry Itsykson
Ivan Monakhov
Alexander Smal
机构：
[1] Steklov Institute of Mathematics at St. Petersburg,
来源：
Theory of Computing Systems | 2012年 / 51卷
关键词：
Propositional proof complexity; Optimal algorithm; i.o. one-way;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajíček and Pudlák (J. Symbol. Logic 54(3):1063, 1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (Theor. Comput. Sci. 412(4–5):478, 2011) recently presented a conjecture implying that such an algorithm does not exist.
引用
收藏
页码：179 / 195
页数：16
相关论文
共 26 条
[1]  
Bogdanov A.(2006)Average-case complexity Found. Trends Theor. Comput. Sci. 2 1-106
[2]  
Trevisan L.(2007)Consequences of the provability of J. Symb. Log. 72 1353-1371
[3]  
Cook S.A.(1979)⊆ J. Symb. Log. 44 36-50
[4]  
Krajíček J.(2006)/ SIGACT News 37 36-54
[5]  
Cook S.A.(2009)The relative efficiency of propositional proof systems Groups, Complexity, Cryptology 1 1-12
[6]  
Reckhow R.A.(2010)Recent work on hierarchies for semantic classes St. Petersburg Math. J. 21 459-468
[7]  
Fortnow L.(1999)A complete public-key cryptosystem SIAM J. Comput. 28 1364-1396
[8]  
Santhanam R.(2010)An infinitely-often one-way function based on an average-case assumption Ann. Pure Appl. Log. 162 213-223
[9]  
Grigoriev D.(1989)A pseudorandom generator from any one-way function J. Symb. Log. 54 1063-1079
[10]  
Hirsch E.A.(2001)Structural complexity of AvgBPP Fundam. Math. 170 123-140
123