scientific article

zbMath0474.68062MaRDI QIDQ3929052

Leslie G. Valiant

Publication date: 1982

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

reductionpolynomialsBoolean functionssubstitutionsubroutinecomputing discrete functions in polynomial timep-definabilitypolynomial analogue of the Meyer-Stockmeyer hierarchy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Polynomials (irreducibility, etc.) (11R09) Other degrees and reducibilities in computability and recursion theory (03D30) Discrete mathematics in relation to computer science (68R99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

Affine projections of symmetric polynomials. ⋮ Boolean circuits versus arithmetic circuits ⋮ Feasible arithmetic computations: Valiant's hypothesis ⋮ There are no p-complete families of symmetric Boolean functions ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Lower bounds for the circuit size of partially homogeneous polynomials ⋮ Resource trade-offs in syntactically multilinear arithmetic circuits ⋮ \(P\) versus \(NP\) and geometry ⋮ Vanishing symmetric Kronecker coefficients ⋮ On the relative power of reduction notions in arithmetic circuit complexity ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Permanent versus determinant: Not via saturations ⋮ \textsf{VNP} = \textsf{VP} in the multilinear world ⋮ On the Expressive Power of Permanents and Perfect Matchings of Matrices of Bounded Pathwidth/Cliquewidth (Extended Abstract) ⋮ Rigid continuation paths II. structured polynomial systems ⋮ On the complexity of scheduling unrelated parallel machines with limited preemptions ⋮ Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ The complexity of partial derivatives ⋮ On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices ⋮ On the algebraic complexity of some families of coloured Tutte polynomials ⋮ A Wronskian approach to the real \(\tau\)-conjecture ⋮ Cook's versus Valiant's hypothesis ⋮ Even partitions in plethysms. ⋮ Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets ⋮ No occurrence obstructions in geometric complexity theory ⋮ A note on the determinant and permanent problem ⋮ Algebraic Complexity Classes ⋮ Unnamed Item ⋮ A \(\tau \)-conjecture for Newton polygons ⋮ A complexity theory of constructible functions and sheaves