scientific article
From MaRDI portal
zbMath0766.68040MaRDI QIDQ4036700
Michael Sipser, Michelangelo Grigni
Publication date: 18 May 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
complete problemsmonotone reducibilityBarrington's gadgetmonotone branching programmonotone complexity classesmonotone computation
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Monotone Boolean formulas can approximate monotone linear threshold functions, Cutting-edge cryptography through the lens of secret sharing, Secret Sharing for mNP: Completeness Results, Unnamed Item, Secret-sharing for NP, Positive First-order Logic on Words and Graphs, Acyclicity programming for sigma-protocols, Distributed Pseudorandom Functions for General Access Structures in NP, Complete problems for monotone NP, Depth Lower Bounds for Monotone Semi-Unbounded Fan-in Circuits, Cutting-Edge Cryptography Through the Lens of Secret Sharing, A recursion-theoretic characterisation of the positive polynomial-time functions, Adventures in monotone complexity and TFNP, Positive versions of polynomial time, Proof complexity of monotone branching programs
