13 found
Sort by:
  1. Pavel Pudlák & Neil Thapen (2012). Alternating Minima and Maxima, Nash Equilibria and Bounded Arithmetic. Annals of Pure and Applied Logic 163 (5):604-614.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Pavel Pudlák (2009). Quantum Deduction Rules. Annals of Pure and Applied Logic 157 (1):16-29.
    We define propositional quantum Frege proof systems and compare them with classical Frege proof systems.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Pavel Pudlák (2003). Parallel Strategies. Journal of Symbolic Logic 68 (4):1242-1250.
    We consider combinatorial principles based on playing several two person games simultaneously. We call strategies for playing two or more games simultaneously parallel. The principles are easy consequences of the determinacy of games, in particular they are true for all finite games. We shall show that the principles fail for infinite games. The statements of these principles are of lower logical complexity than the sentence expressing the determinacy of games, therefore, they can be studied in weak axiomatic systems for arithmetic (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  4. Samuel R. Buss & Pavel Pudlák (2001). On the Computational Content of Intuitionistic Propositional Proofs. Annals of Pure and Applied Logic 109 (1-2):49-64.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Pavel Pudlák (1999). A Note on Applicability of the Incompleteness Theorem to Human Mind. Annals of Pure and Applied Logic 96 (1-3):335-342.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  6. Pavel Pudlák (1997). Lower Bounds for Resolution and Cutting Plane Proofs and Monotone Computations. Journal of Symbolic Logic 62 (3):981-998.
    We prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. The latter result is of independent interest, since, in particular, it implies an exponential lower bound for some arithmetic circuits.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  7. Jan Krajíček, Pavel Pudlák & Gaisi Takeuti (1991). Bounded Arithmetic and the Polynomial Hierarchy. Annals of Pure and Applied Logic 52 (1-2):143-153.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  8. Jan Krajíček & Pavel Pudlák (1990). Quantified Propositional Calculi and Fragments of Bounded Arithmetic. Mathematical Logic Quarterly 36 (1):29-46.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  9. Jan Krajíček & Pavel Pudlák (1989). On the Structure of Initial Segments of Models of Arithmetic. Archive for Mathematical Logic 28 (2):91-98.
    For any countable nonstandard modelM of a sufficiently strong fragment of arithmeticT, and any nonstandard numbersa, c εM, M⊨c≦a, there is a modelK ofT which agrees withM up toa and such that inK there is a proof of contradiction inT with Gödel number $ \leqq 2^{a^c } $.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Jan Krajíček & Pavel Pudlák (1989). Propositional Proof Systems, the Consistency of First Order Theories and the Complexity of Computations. Journal of Symbolic Logic 54 (3):1063-1079.
    We consider the problem about the length of proofs of the sentences $\operatorname{Con}_S(\underline{n})$ saying that there is no proof of contradiction in S whose length is ≤ n. We show the relation of this problem to some problems about propositional proof systems.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  11. Jan Krajíček & Pavel Pudlák (1988). The Number of Proof Lines and the Size of Proofs in First Order Logic. Archive for Mathematical Logic 27 (1):69-84.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  12. Pavel Pudlak (1988). Review: Edward Nelson, Predicative Arithmetic. [REVIEW] Journal of Symbolic Logic 53 (3):987-989.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  13. Pavel Pudlák (1985). Cuts, Consistency Statements and Interpretations. Journal of Symbolic Logic 50 (2):423-441.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation