scientific article; zbMATH DE number 1114028

MaRDI QIDQ4375799zbMATH OpenFDO

Authors Pavel Pudlák, Jiří Sgall

Publication date 1 March 1998

zbMATH Keywords

algebraic models of computationcircuit complexityinterpolation of polynomialslower boundsNullstellen refutationspan program

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1059248
• Publication:5748889
• Algebraic proof systems over formulas.
• Interpolation in Valiant's theory
• Superpolynomial lower bounds for monotone span programs

Cited in

(17)

• No feasible monotone interpolation for simple combinatorial reasoning
• From private simultaneous messages to zero-information Arthur-Merlin protocols and back
• On the automatizability of resolution and related propositional proof systems
• On the automatizability of polynomial calculus
• On arithmetic branching programs
• Nullstellensatz size-degree trade-offs from reversible pebbling
• A framework for space complexity in algebraic proof systems
• scientific article; zbMATH DE number 4092761 (Why is no real title available?)
• Adventures in monotone complexity and TFNP
• Nullstellensatz size-degree trade-offs from reversible pebbling
• scientific article; zbMATH DE number 4182832 (Why is no real title available?)
• Proof complexity of non-classical logics
• On the computational content of intuitionistic propositional proofs
• Feasible interpolation for polynomial calculus and sums-of-squares
• On protocols for monotone feasible interpolation
• Mean-payoff games and propositional proofs
• Nondeterministic functions and the existence of optimal proof systems

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 Q4375799)