The network complexity and the Turing machine complexity of finite functions

DOI10.1007/BF00265223zbMath0338.02019OpenAlexW2122786581MaRDI QIDQ1230622

Claus Peter Schnorr

Publication date: 1976

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00265223

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Turing machines and related notions (03D10)

Related Items (28)

Complete divisibility problems for slowly utilized oracles ⋮ The complexity of depth-3 circuits computing symmetric Boolean functions ⋮ Parallel algorithms for solvable permutation groups ⋮ Complexity theory of parallel time and hardware ⋮ RelativizedNC ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Unnamed Item ⋮ A 3n-lower bound on the network complexity of Boolean functions ⋮ On the simulation of quantum Turing machines. ⋮ On uniform circuit complexity ⋮ Classifying the computational complexity of problems ⋮ On the complexity of 2-output Boolean networks ⋮ The equivalence of Horn and network complexity for Boolean functions ⋮ Compositional complexity of Boolean functions ⋮ The complexity of deciding reachability properties of distributed negotiation schemes ⋮ The complexity of contract negotiation ⋮ A survey of space complexity ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ A lower bound on the number of additions in monotone computations ⋮ Information and computation: Classical and quantum aspects ⋮ Nonuniform complexity classes specified by lower and upper bounds ⋮ A lower bound for the complexity of Craig's interpolants in sentential logic ⋮ Characterization of all optimal networks for a simultaneous computation of AND and NOR ⋮ Complex Boolean networks obtained by diagonalization ⋮ PAC-learning gains of Turing machines over circuits and neural networks ⋮ Uncontrollable computational growth in theoretical physics ⋮ Multi-head finite automata: Data-independent versus data-dependent computations ⋮ On the computational complexity of qualitative coalitional games

Cites Work

• Two-Tape Simulation of Multitape Turing Machines
• Computational Work and Time on Finite Machines
• Unnamed Item
• Unnamed Item

This page was built for publication: The network complexity and the Turing machine complexity of finite functions