DEHN FUNCTION AND LENGTH OF PROOFS

DOI10.1142/S0218196703001523zbMath1043.03045MaRDI QIDQ4464963

Jan Krajíček

Publication date: 27 May 2004

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

zbMATH Keywords

proof complexityDehn function

Mathematics Subject Classification ID

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

Related Items

Group cancellation and resolution

Cites Work

• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Reductions and functors from problems to word problems
• Isoperimetric functions of groups and computational complexity of the word problem
• Subgroups of finitely presented groups
• THE DOUBLE EXPONENTIAL THEOREM FOR ISODIAMETRIC AND ISOPERIMETRIC FUNCTIONS
• ISODIAMETRIC AND ISOPERIMETRIC INEQUALITIES FOR GROUP PRESENTATIONS
• Every Prime Has a Succinct Certificate
• The relative efficiency of propositional proof systems
• Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• The Complexity of Propositional Proofs
• The word problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item