DEHN FUNCTION AND LENGTH OF PROOFS

DOI10.1142/S0218196703001523MaRDI QIDQ4464963zbMATH OpenFDO

Authors Jan Krajíček

Publication date 27 May 2004

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0218196703001523

zbMATH Keywords

Dehn functionproof complexity

Mathematics Subject Classification ID

Complexity of proofs (03F20) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites work

• Every Prime Has a Succinct Certificate
• scientific article; zbMATH DE number 437296 (Why is no real title available?)
• scientific article; zbMATH DE number 3920761 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1822302 (Why is no real title available?)
• ISODIAMETRIC AND ISOPERIMETRIC INEQUALITIES FOR GROUP PRESENTATIONS
• Isoperimetric functions of groups and computational complexity of the word problem
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Reductions and functors from problems to word problems
• Subgroups of finitely presented groups
• The Complexity of Propositional Proofs
• THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
• The relative efficiency of propositional proof systems
• The word problem
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem

Cited in

(1)

• Group cancellation and resolution

This page was built for publication: DEHN FUNCTION AND LENGTH OF PROOFS

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