Reducibility by algebraic projections

zbMath0493.68045MaRDI QIDQ1168734

Leslie G. Valiant

Publication date: 1982

Published in: L'Enseignement Mathématique. 2e Série (Search for Journal in Brave)

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

An introduction to parallelism in combinatorial optimization ⋮ Fast computation of discrete invariants associated to a differential rational mapping ⋮ Sparktope: linear programs from algorithms ⋮ Counting quantifiers, successor relations, and logarithmic space ⋮ The power of nondeterminism in polynomial-size bounded-width branching programs ⋮ Gap-languages and log-time complexity classes ⋮ On \(\epsilon\)-sensitive monotone computations ⋮ Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators ⋮ A probabilistic algorithm to test local algebraic observability in polynomial time ⋮ Expressing combinatorial optimization problems by linear programs ⋮ Finding Reductions Automatically ⋮ Nonvanishing of Kronecker coefficients for rectangular shapes. ⋮ Functions computable in polynomial space ⋮ From a zoo to a zoology: Towards a general theory of graph polynomials ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity ⋮ Polynomial size linear programs for problems in \textsc{P}