scientific article; zbMATH DE number 3936520
[For the entire collection see Zbl 0553.00001.] Our purpose here is to give a brief discussion of a very strict notion of reducibility called p-projection. Further details can be found e.g. in the author's papers in Proc. 11th ACM Symp. Theory of Computing, 249-261 (1979) and in Logic and algorithmic. Monogr. L'Enseign. Math. 30, 365-380 (1982; Zbl 0474.68062). The remarkable property of this notion of reduction is that in spite of its demanding and restricted nature numerous natural problems that superficially look dissimilar can be related by it. It is applicable to a variety of algebraic structures among which rings of multivariate polynomials and Boolean algebras are important examples. It can be used to give an account to the relative difficulty of computational problems almost without having to define models of computation.
- Abstract algebraic structure of analytic theory of algorithms
- Algorithmic complexity of the problem of occurrence in commutants and members of the lower central series
- Additive complexity in directed computations
- On computation complexity problems concerning relation algebras
- Completeness and reduction in algebraic complexity theory
- On the relative power of reduction notions in arithmetic circuit complexity
- Wildness for tensors
- Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda's theorem
- Algebraic dependence in generating functions and expansion complexity
- Computational complexity of learning algebraic varieties
- On the complexity of the differential-algebraic description of analytic complexity classes
- A complexity theory of constructible functions and sheaves
- Complexity of the normalization of algebras
- An algebraic approach to computations with progress
- First-order reduction and computational complexity
- scientific article; zbMATH DE number 3858462 (Why is no real title available?)
- scientific article; zbMATH DE number 3872682 (Why is no real title available?)
- scientific article; zbMATH DE number 7295748 (Why is no real title available?)
- Counting complexity classes for numeric computations II
- A complexity theory based on Boolean algebra
- scientific article; zbMATH DE number 3637838 (Why is no real title available?)
- An algebraic approach to communication complexity
- scientific article; zbMATH DE number 7150624 (Why is no real title available?)
- Integer complexity: algorithms and computational results
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- An affine representation of de Casteljau's and de Boor's rational algorithms
- A framework for solving VLSI graph layout problems
- On the algebraic complexity of set equality and inclusion
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)