scientific article; zbMATH DE number 1114028
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].
- No feasible monotone interpolation for simple combinatorial reasoning
- From private simultaneous messages to zero-information Arthur-Merlin protocols and back
- On the automatizability of resolution and related propositional proof systems
- On the automatizability of polynomial calculus
- On arithmetic branching programs
- Nullstellensatz size-degree trade-offs from reversible pebbling
- A framework for space complexity in algebraic proof systems
- scientific article; zbMATH DE number 4092761 (Why is no real title available?)
- Adventures in monotone complexity and TFNP
- Nullstellensatz size-degree trade-offs from reversible pebbling
- scientific article; zbMATH DE number 4182832 (Why is no real title available?)
- Proof complexity of non-classical logics
- On the computational content of intuitionistic propositional proofs
- Feasible interpolation for polynomial calculus and sums-of-squares
- On protocols for monotone feasible interpolation
- Mean-payoff games and propositional proofs
- Nondeterministic functions and the existence of optimal proof systems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4375799)