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 条

[11]

Pervyshev K.(2001)Propositional proof systems, the consistency of first order theories and the complexity of computations Bull. Symb. Log. 7 197-212

[12]

Hirsch E.A.(1973)On the weak pigeonhole principle Probl. Inf. Transm. 9 265-266

[13]

Itsykson D.M.(1987)Tautologies from pseudorandom generators Combinatorica 7 357-363

[14]

Håstad J.(2011)Universal sequential search problems Theor. Comput. Sci. 412 478-481

[15]

Impagliazzo R.(2003)One-way functions and pseudorandom generators Theor. Comput. Sci. 295 323-339

[16]

Levin L.A.(undefined)Speedup for natural problems and noncomputability undefined undefined undefined-undefined

[17]

Luby M.(undefined)On reducibility and symmetry of disjoint NP pairs undefined undefined undefined-undefined

[18]

Itsykson D.M.(undefined)undefined undefined undefined undefined-undefined

[19]

Krajíček J.(undefined)undefined undefined undefined undefined-undefined

[20]

Pudlák P.(undefined)undefined undefined undefined undefined-undefined

← 1 2 3 →