No label defined (Q4375799)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1114028
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1114028

      Statements

      0 references
      0 references
      1 March 1998
      0 references
      span program
      0 references
      interpolation of polynomials
      0 references
      Nullstellen refutation
      0 references
      circuit complexity
      0 references
      algebraic models of computation
      0 references
      lower bounds
      0 references
      The authors consider the algebraic models of computation: dependency, span, and polynomial programs (abbreviated DP, SP, and PP, respectively). The first two are about labelled matrices over a field \(K\), where \(K\) is \(\text{GF}(p)\), \(\mathbb{Q}\) or \(\mathbb{R}\). Their rows are labelled by \(x_i\), \(1-x_i\), or 1. Under a truth value assignment to \(x\)'s (1 for truth, and 0 for falsity), those row vectors are selected whose labels become 1. The DP [SP] takes the value 1 if the selected vectors [together with \(e=\langle 1,0, \dots, 0\rangle]\) are linearly dependent. A PP is given by a set of labelled polynomials in \(K[{\mathbf y}]\). Under a truth value assigment to \(x\)'s, the program takes the value 1 when there is polynomial refutation of the selected polynomials, namely a non-zero constant polynomial can be obtained from them by linear combinations and the operation \(q \mapsto {\mathbf y} q\). The first half of the paper is about the relative strengths of those and other computation devices. A simple Boolean function \(f_0\) is exhibited whose \(\text{mDP} (f_0)\), the minimum size of monotone DP, is exponential. The authors show that \(\text{SP}(\neg f)\leq n-\text{SP} (f)\) where \(n\) is the arity of \(f\), relations between \(\text{DP}(f)\) and \(\text{SP}(f)\), and mutual simulations of PP's and Boolean circuits. The second half of the paper is about interpolation theorems of polynomials. When a set of polynomials \(p_i ({\mathbf x}, {\mathbf y})\) and \(q_j ({\mathbf x}, {\mathbf z})\), where \({\mathbf y}\) and \({\mathbf z}\) are disjoint, has a Nullstellen refutation, then there is an SP \(C\) on \({\mathbf x}\) with the property that if \(C\) accepts \({\mathbf u}\in\{0,1\}^n\), then \(p_i ({\mathbf x}, {\mathbf y}) =0\) are not satisfiable, and if \(C\) does not accept, then \(q_j ({\mathbf x}, {\mathbf z}) =0\) is not satisfiable. And conversely, an SP is described by a Nullstellen system. Besides these definite results, the authors comment on how to use interpolation theorems to determine lower bounds, on what happens when the base field is changed, and on recent achievements. The paper closes with a section on open problems. For the entire collection see [Zbl 0881.00033].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references