نتائج البحث

Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds ...

• Authors : Khaniki, Erfan

Subjects: Proof complexity; Bounded arithmetic; Bounded depth Frege

تفاصيل العنوان

From Classical Proof Theory to P versus NP: a Guide to Bounded Theories (Invited Talk) ...

• Authors : Tzameret, Iddo

Subjects: Bounded arithmetic; complexity class separations; circuit complexity

تفاصيل العنوان

On the pigeonhole and the modular counting principles over the bounded arithmetic $V^{0}$ (Theory and Applications of Proof and Computation)

• Authors : Ken, Eitetsu

Subjects: pigeonhole principle; uniform counting principle; V⁰

• Source: 数理解析研究所講究録. 2228:186-205

تفاصيل العنوان

Feasibly constructive proofs of succinct weak circuit lower bounds

• Authors : Muller, Moritz Martin; Pich, Ján; Universitat Politècnica de Catalunya. Departament de Ciències de la Computació

Subjects: Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat; Polynomials; Computational complexity

تفاصيل العنوان

Proof Complexity (Dagstuhl Seminar 18051)

• Authors : Atserias, Albert; Santhanam, Rahul

Subjects: bounded arithmetic; computational complexity; logic

• Source: Dagstuhl Reports, Volume 8, Issue 1; ISSN 2192-5283

تفاصيل العنوان

Uniform, integral and efficient proofs for the determinant identities

• Authors : Tzameret, Iddo; Cook, Stephen

Subjects: Bounded Arithmetic; Computational Complexity; proof complexity

• Source: Tzameret , I & Cook , S 2017 , Uniform, integral and efficient proofs for the determinant identities . in 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) . vol. 32 , IEEE , pp.

تفاصيل العنوان

Lower bounds for DNF-refutations of a relativized weak pigeonhole principle

• Authors : Atserias, Albert; Müller, Moritz; Oliva Valls, Sergi ...

Subjects: Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica; Computational complexity; Proof complexity

تفاصيل العنوان

Partially definable forcing and bounded arithmetic

• Authors : Atserias, Albert; Müller, Moritz;

Subjects: Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica; Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi matemàtica; Computational complexity

تفاصيل العنوان

Theories for Subexponential-size Bounded-depth Frege Proofs ...

• Authors : Ghasemloo, Kaveh; Cook, Stephen A.

Subjects: Computational Complexity Theory; Proof Complexity; Bounded Arithmetic

تفاصيل العنوان

Construction of models of bounded arithmetic by restricted reduced powers

• Authors : Michal Garlík

Subjects: Discrete mathematics; Bounded arithmetic; Logic

• Source: Archive for Mathematical Logic. 55:625-648

تفاصيل العنوان