On uniform circuit complexity

DOI10.1016/0022-0000(81)90038-6zbMath0462.68013OpenAlexW2027501230MaRDI QIDQ1152951

Publication date: 1981

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90038-6

zbMATH Keywords

parallel complexity alternating Turing machines context-free language recognition

Mathematics Subject Classification ID

Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).

Related Items (only showing first 100 items - show all)

Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs ⋮ Local Reductions ⋮ Expander Construction in VNC1 ⋮ On the synchronization of semi-traces ⋮ A note on some languages in uniform $ACC^ 0$ ⋮ An algebra and a logic for $NC^ 1$ ⋮ Boolean circuits versus arithmetic circuits ⋮ On uniformity within $NC^ 1$ ⋮ Ranking and formal power series ⋮ Rounds versus time for the two person pebble game ⋮ Some results on uniform arithmetic circuit complexity ⋮ Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines ⋮ Reversals and alternation ⋮ Parallel complexity of iterated morphisms and the arithmetic of small numbers ⋮ The emptiness problem for intersections of regular languages ⋮ On languages accepted with simultaneous complexity bounds and their ranking problem ⋮ RelativizedNC ⋮ On parallel hierarchies and R ki ⋮ Computation models and function algebras ⋮ Characterizing parallel time by type 2 recursions with polynomial output length ⋮ A Characterization of NC k by First Order Functional Programs ⋮ Complexity and Algorithms for Well-Structured k-SAT Instances ⋮ Separating $\oplus L$ from $L, NL,$ co-$NL$, and $AL = P$ for oblivious Turing machines of linear access ⋮ On log-time alternating Turing machines of alternation depth k ⋮ Embedding arbitrary Boolean circuits into fungal automata ⋮ Subclasses of \textsc{Ptime} interpreted by programming languages ⋮ On homomorphic images of the Szilard languages of matrix insertion-deletion systems with matrices of size 2 ⋮ Adaptive logspace reducibility and parallel time ⋮ Nondeterministic auxiliary depth-bounded storage automata and semi-unbounded fan-in cascading circuits (extended abstract) ⋮ Parallelizing time with polynomial circuits ⋮ Classifying the computational complexity of problems ⋮ Two-way automata and length-preserving homomorphisms ⋮ Recursion Schemata for NC k ⋮ Extensional Uniformity for Boolean Circuits ⋮ On some derivation mechanisms and the complexity of their Szilard languages ⋮ Complexity theory for splicing systems ⋮ Circuit complexity of regular languages ⋮ The complexity of ranking simple languages ⋮ Division in logspace-uniformNC¹ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02 ⋮ Fine-grained cryptography revisited ⋮ Reductions to Graph Isomorphism ⋮ A recursion-theoretic characterisation of the positive polynomial-time functions ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ The Computational Complexity of Choice Sets ⋮ Unnamed Item ⋮ The lexicographically first maximal subgraph problems:P-completeness andNC algorithms ⋮ On the Complexity of Szilard Languages of Regulated Grammars ⋮ The enumerability of P collapses P to NC ⋮ Rounds versus time for the two person pebble game ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity ⋮ Two function algebras defining functions in $\mathsf{NC}^k$ Boolean circuits ⋮ Function-algebraic characterizations of log and polylog parallel time ⋮ Parallel pointer machines ⋮ Space-efficient recognition of sparse self-reducible languages ⋮ On the complexity of inducing categorical and quantitative association rules ⋮ The equivalence of theories that characterize ALogTime ⋮ Boolean grammars ⋮ Array processing machines: an abstract model ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ Local reduction ⋮ On nondeterminism in parallel computation ⋮ ALOGTIME and a conjecture of S. A. Cook ⋮ Expressing uniformity via oracles ⋮ Parallel computation with threshold functions ⋮ An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits ⋮ Decompositions of nondeterministic reductions ⋮ Parallel evaluation of arithmetic circuits ⋮ Some subclasses of context-free languages in $NC^ 1$ ⋮ Efficient parallel circuits and algorithms for division ⋮ A measure of relativized space which is faithful with respect to depth ⋮ Subtree isomorphism is NC reducible to bipartite perfect matching ⋮ Complexity theory of parallel time and hardware ⋮ Bounded-width polynomial-size branching programs recognize exactly those languages in $NC^ 1$ ⋮ Uniform proofs of ACC representations ⋮ On parallel hierarchies and $R_k^i$ ⋮ Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs ⋮ On the relative complexity of some languages in $NC^ 1$ ⋮ Gap-languages and log-time complexity classes ⋮ Conjunctive and Boolean grammars: the true general case of the context-free grammars ⋮ On the parallel complexity of loops ⋮ Expander construction in $\mathrm{VNC}^1$ ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Bounded size dictionary compression: SC$^{k}$-completeness and NC algorithms. ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ On theories of bounded arithmetic for $\mathrm{NC}^1$ ⋮ A sorting network in bounded arithmetic ⋮ Parallel complexity of the regular code problem ⋮ Parallel models of computation: An introductory survey ⋮ The complexity of short two-person games ⋮ An $\mathsf{AC}^{1}$-complete model checking problem for intuitionistic logic ⋮ Properties that characterize LOGCFL ⋮ Arithmetizing uniform $NC$ ⋮ The complexity of computing the number of strings of given length in context-free languages ⋮ Lower bounds against weakly-uniform threshold circuits

Cites Work

This page was built for publication: On uniform circuit complexity