Negation can be exponentially powerful
type: Item
instance of: scholarly article
title: Negation can be exponentially powerful
zbMATH Open document ID: 0442.68030
DOI: 10.1016/0304-3975(80)90060-2
published in: Theoretical Computer Science
publication date: 1980-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3690684
zbMATH Keywords: computing multivariate polynomials
zbMATH Keywords: cancellation of terms
zbMATH Keywords: algebraic algorithms
zbMATH Keywords: counting perfect matchings in planar graphs
zbMATH Keywords: negations
author: Leslie G. Valiant
MaRDI profile type: Publication
full work available at URL: 0304-3975(80)90060-2
OpenAlex ID: W1966757974
cites work: Q3941433
cites work: Q4190138
cites work: Matrix tree theorems
cites work: Q4195939
cites work: Q4092993
cites work: Statistical Mechanics of Dimers on a Plane Lattice
cites work: On the parallel evaluation of multivariate polynomials
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5605168
cites work: Q4130999
cites work: Monotone switching circuits and Boolean matrix product
cites work: Complexity of monotone networks for Boolean matrix product
cites work: Combinatorial methods
cites work: Shifting Graphs and Their Applications
cites work: The Power of Negative Thinking in Multiplying Boolean Matrices
cites work: Q4138141
cites work: A lower bound on the number of additions in monotone computations
cites work: Gaussian elimination is not optimal
cites work: Q4047029
cites work: Switching functions whose monotone complexity
description: scientific article; zbMATH DE number 3690684