David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Bulletin of Symbolic Logic 7 (2):197-212 (2001)
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)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Olaf Beyersdorff (2009). On the Correspondence Between Arithmetic Theories and Propositional Proof Systems - a Survey. Mlq 55 (2):116-137.
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 downloads3 ( #290,439 of 1,098,982 )
Recent downloads (6 months)1 ( #287,052 of 1,098,982 )
How can I increase my downloads?