The network complexity and the Turing machine complexity of finite functions

DOI10.1007/BF00265223MaRDI QIDQ1230622zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• Computational Work and Time on Finite Machines
• scientific article; zbMATH DE number 3471609 (Why is no real title available?)
• scientific article; zbMATH DE number 3313256 (Why is no real title available?)
• Two-Tape Simulation of Multitape Turing Machines

Cited in

(30)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1230622)