scientific article; zbMATH DE number 3607492

zbMath0391.68025MaRDI QIDQ4172915

John E. Savage

Publication date: 1976

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

ComplexityTuring MachinesComputational ComplexitySequential MachinesNp- CompleteCircuit ComplexityTime-Space Tradeoffs

Mathematics Subject Classification ID

Related Items (53)

Algebraic nonlinearity and its applications to cryptography ⋮ An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph ⋮ The complexity of error-correcting codes ⋮ One-way functions and circuit complexity ⋮ On the complexity of unitary transformations ⋮ On the parallel complexity of linear groups ⋮ Limits on the power of concurrent-write parallel machines ⋮ On the Complexity of Multivalued Logic Functions over Some Infinite Basis ⋮ On characterizations of the class PSPACE/poly ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ Simulation of circuits of functional elements by the universal Turing machine ⋮ Random problems ⋮ Feasible arithmetic computations: Valiant's hypothesis ⋮ Depth of Boolean functions realized by circuits over an arbitrary infinite basis ⋮ Construction of universal enumerators and formulas for threshold functions ⋮ Size-depth tradeoff in non-monotone Boolean formulae ⋮ Asymptotics of growth for non-monotone complexity of multi-valued logic function systems ⋮ Unnamed Item ⋮ A 3n-lower bound on the network complexity of Boolean functions ⋮ Improvement of nonmonotone complexity estimates of \(k\)-valued logic functions ⋮ Parallelizable algebras ⋮ Probabilistic satisfiability: algorithms with the presence and absence of a phase transition ⋮ Feebly secure cryptographic primitives ⋮ Circuit complexity of linear functions: gate elimination and feeble security ⋮ Polynomial size \(\Omega\)-branching programs and their computational power ⋮ Two-way automata and length-preserving homomorphisms ⋮ Space-bounded quantum complexity ⋮ An improved algorithm for finding saddlepoints of two-person zero-sum games ⋮ ON THE COMPLEXITY OF CIRCUITS IN BASES CONTAINING MONOTONE ELEMENTS WITH ZERO WEIGHTS ⋮ IMPROVEMENT OF THE LOWER BOUND FOR THE COMPLEXITY OF EXPONENTIATION ⋮ ON THE MEANING OF WORKS BY V. M. KHRAPCHENKO ⋮ On the size of binary decision diagrams representing Boolean functions ⋮ Gate Elimination for Linear Functions and New Feebly Secure Constructions ⋮ The minimum number of negations in circuits for systems of multi-valued functions ⋮ Parity, circuits, and the polynomial-time hierarchy ⋮ Prolegomenon to the relation between social theory and method* ⋮ Optimal interconnection in digital systems satisfying concurrency constraints ⋮ Constructive universal algebra: An introduction ⋮ A curious new result in switching theory ⋮ On the depth of \(k\)-valued logic functions over arbitrary bases ⋮ On Bellman's and Knuth's problems and their generalizations ⋮ ON THE CONNECTION BETWEEN THE COMPLEXITY AND CREDIBILITY OF INFERRED MODELS ⋮ Relation between two measures of the computation complexity for systems of monomials ⋮ Depth of functions of the \(k\)-valued logic in infinite bases ⋮ Improved processor bounds for combinatorial problems in RNC ⋮ A Feebly Secure Trapdoor Function ⋮ Exact value of the nonmonotone complexity of Boolean functions ⋮ On the complexity of computation of a pair of monomials in two variables ⋮ Nonuniform complexity classes specified by lower and upper bounds ⋮ A lower bound for the complexity of Craig's interpolants in sentential logic ⋮ Nearly optimal hierarchies for network and formula size ⋮ Non-uniform automata over groups ⋮ Decomposition of graphs and monotone formula size of homogeneous functions

This page was built for publication: