17 found
Order:
  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.
  2. 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 (8 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  3.  1
    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.
    T i 2 = S i +1 2 implies ∑ p i +1 ⊆ Δ p i +1 ⧸poly. S 2 and IΔ 0 ƒ are not finitely axiomatizable. The main tool is a Herbrand-type witnessing theorem for ∃∀∃ П b i -formulas provable in T i 2 where the witnessing functions are □ p i +1.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   20 citations  
  4.  13
    Pavel Pudlák (1985). Cuts, Consistency Statements and Interpretations. Journal of Symbolic Logic 50 (2):423-441.
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography   20 citations  
  5.  5
    Jan Krajíček & Pavel Pudlák (1990). Quantified Propositional Calculi and Fragments of Bounded Arithmetic. Mathematical Logic Quarterly 36 (1):29-46.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   12 citations  
  6.  4
    Jan Krajíček & Pavel Pudlák (1990). Quantified Propositional Calculi and Fragments of Bounded Arithmetic. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 36 (1):29-46.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   6 citations  
  7.  7
    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.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   10 citations  
  8.  6
    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 (8 more)  
     
    Export citation  
     
    My bibliography   8 citations  
  9. Jan Mycielski, Pavel Pudlák, Alan S. Stern & American Mathematical Society (1990). A Lattice of Chapters of Mathematics. American Mathematical Society.
     
    Export citation  
     
    My bibliography   5 citations  
  10.  1
    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.
    The paper proves refined feasibility properties for the disjunction property of intuitionistic propositional logic. We prove that it is possible to eliminate all cuts from an intuitionistic proof, propositional or first-order, without increasing the Horn closure of the proof. We obtain a polynomial time, interactive, realizability algorithm for propositional intuitionistic proofs. The feasibility of the disjunction property is proved for sequents containing Harrop formulas. Under hardness assumptions for NP and for factoring, it is shown that the intuitionistic propositional calculus does (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  11.  10
    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 } $.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  12.  8
    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)  
     
    Export citation  
     
    My bibliography  
  13.  2
    Pavel Pudlák (2015). On the Complexity of Finding Falsifying Assignments for Herbrand Disjunctions. Archive for Mathematical Logic 54 (7-8):769-783.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  14.  1
    Pavel Pudlak (1988). Review: Edward Nelson, Predicative Arithmetic. [REVIEW] Journal of Symbolic Logic 53 (3):987-989.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  15.  4
    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)  
     
    Export citation  
     
    My bibliography  
  16. Pavel Pudlák (1988). Nelson Edward. Predicative Arithmetic. Mathematical Notes, No. 32. Princeton University Press, Princeton 1986, Viii + 189 Pp. [REVIEW] Journal of Symbolic Logic 53 (3):987-989.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  17. 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)  
     
    Export citation  
     
    My bibliography