Graduate studies at Western
Bulletin of Symbolic Logic 7 (2):197-212 (2001)
|Abstract||We consider tautologies formed form a pseudo-random number generator, defined in Krajicek  and in Alekhnovich et al. . We explain a strategy of proving their hardness for Extended Frege systems via a conjecture about bounded arithmetic formulated in Krajicek . Further we give a purely finitary statement, in the form of a hardness condition imposed on a function, equivalent to the conjecture. This is accompanied by a brief explanation, aimed at non-specialists, of the relation between prepositional proof complexity and bounded arithmetic|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Teddy Seidenfeld, Mark Schervish & Joseph Kadane, When Coherent Preferences May Not Preserve Indifference Between Equivalent Random Variables: A Price for Unbounded Utilities.
Jan Krajíček, Alan Skelley & Neil Thapen (2007). NP Search Problems in Low Fragments of Bounded Arithmetic. Journal of Symbolic Logic 72 (2):649 - 672.
Jan Krajíček (1997). Interpolation Theorems, Lower Bounds for Proof Systems, and Independence Results for Bounded Arithmetic. Journal of Symbolic Logic 62 (2):457-486.
Teddy Seidenfeld, On the Equivalence of Conglomerability and Disintegrability for Unbounded Random Variables.
Pavel Hrubeš (2007). Lower Bounds for Modal Logics. Journal of Symbolic Logic 72 (3):941 - 958.
William A. Dembski (1991). Randomness by Design. Noûs 25 (1):75-106.
Claes Strannegård, Simon Ulfsbäcker, David Hedqvist & Tommy Gärling (2010). Reasoning Processes in Propositional Logic. Journal of Logic, Language and Information 19 (3):283-314.
Jan Krajíček (1995). Bounded Arithmetic, Propositional Logic, and Complexity Theory. Cambridge University Press.
Jan Krajíček (2004). Dual Weak Pigeonhole Principle, Pseudo-Surjective Functions, and Provability of Circuit Lower Bounds. Journal of Symbolic Logic 69 (1):265 - 286.
Added to index2009-01-28
Total downloads2 ( #246,694 of 739,401 )
Recent downloads (6 months)1 ( #61,680 of 739,401 )
How can I increase my downloads?