Publication:3929052
From MaRDI portal
zbMath0474.68062MaRDI QIDQ3929052
Publication date: 1982
reduction; polynomials; Boolean functions; substitution; subroutine; computing discrete functions in polynomial time; p-definability; polynomial analogue of the Meyer-Stockmeyer hierarchy
68Q25: Analysis of algorithms and problem complexity
90C05: Linear programming
11R09: Polynomials (irreducibility, etc.)
03D30: Other degrees and reducibilities in computability and recursion theory
68R99: Discrete mathematics in relation to computer science
03D60: Computability and recursion theory on ordinals, admissible sets, etc.
Related Items
On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices, Algorithmic uses of the Feferman-Vaught theorem, Feasible arithmetic computations: Valiant's hypothesis, There are no p-complete families of symmetric Boolean functions, The complexity of partial derivatives, A note on the determinant and permanent problem, On the algebraic complexity of some families of coloured Tutte polynomials, Affine projections of symmetric polynomials., Cook's versus Valiant's hypothesis, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Boolean circuits versus arithmetic circuits, On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract)
