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
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
0.7546350359916687
0 references
0.7540153861045837
0 references
0.7516171336174011
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