scientific article; zbMATH DE number 65749

MaRDI QIDQ4010360zbMATH OpenFDO

Authors Jan Krajíček

Publication date 27 September 1992

zbMATH Keywords

bounded arithmeticfragments of arithmeticinteractive computationno counter-example interpretationwitnessing theorem

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Second- and higher-order arithmetic and fragments (03F35)

Recommendations

• On the No-Counterexample Interpretation
• scientific article; zbMATH DE number 1794691
• scientific article; zbMATH DE number 1956569
• Tools and Algorithms for the Construction and Analysis of Systems
• Counterexample without cases
• scientific article; zbMATH DE number 2062231
• No feasible monotone interpolation for simple combinatorial reasoning
• scientific article; zbMATH DE number 4102471
• On the computation of counterexamples in compositional nonblocking verification
• Interaction and depth against nondeterminism in proof search

Cited in

(9)

• Relating the bounded arithmetic and polynomial time hierarchies
• Circuit principles and weak pigeonhole variants
• Upper and lower Ramsey bounds in bounded arithmetic
• scientific article; zbMATH DE number 65757 (Why is no real title available?)
• Satisfiability, branch-width and Tseitin tautologies
• Circuit lower bounds in bounded arithmetics
• Approximate counting and NP search problems
• On the consistency of circuit lower bounds for non-deterministic time
• Prime factorization in models of \(\mathrm{PV}_1\)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4010360)