scientific article; zbMATH DE number 3936520

MaRDI QIDQ3707409zbMATH OpenFDO

Authors Leslie G. Valiant

Publication date 1984

zbMATH Keywords

reducibilityalgebraic structuresp-projectionrelative difficulty of computational problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A complexity theory based on Boolean algebra
• Computational complexity in algebraic systems
• Constant Depth Reducibility
• On the relative power of reduction notions in arithmetic circuit complexity
• Complexity classes and completeness in algebraic geometry

Cited in

(28)

• Counting complexity classes for numeric computations II
• scientific article; zbMATH DE number 7295748 (Why is no real title available?)
• A complexity theory of constructible functions and sheaves
• An affine representation of de Casteljau's and de Boor's rational algorithms
• On the algebraic complexity of set equality and inclusion
• On computation complexity problems concerning relation algebras
• Computational complexity of learning algebraic varieties
• Wildness for tensors
• Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem
• scientific article; zbMATH DE number 1223708 (Why is no real title available?)
• scientific article; zbMATH DE number 7150624 (Why is no real title available?)
• An algebraic approach to computations with progress
• Additive complexity in directed computations
• On the relative power of reduction notions in arithmetic circuit complexity
• Integer complexity: algorithms and computational results
• On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
• Algebraic dependence in generating functions and expansion complexity
• A framework for solving VLSI graph layout problems
• Completeness and reduction in algebraic complexity theory
• scientific article; zbMATH DE number 3858462 (Why is no real title available?)
• Complexity of the normalization of algebras
• A complexity theory based on Boolean algebra
• First-order reduction and computational complexity
• Algorithmic complexity of the problem of occurrence in commutants and members of the lower central series
• Abstract algebraic structure of analytic theory of algorithms
• On the complexity of the differential-algebraic description of analytic complexity classes
• scientific article; zbMATH DE number 3637838 (Why is no real title available?)
• scientific article; zbMATH DE number 3872682 (Why is no real title available?)

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