A complexity theory based on Boolean algebra
From MaRDI portal
Publication:3771612
DOI10.1145/3149.3158zbMath0633.68032OpenAlexW2089857781WikidataQ128705256 ScholiaQ128705256MaRDI QIDQ3771612
No author found.
Publication date: 1985
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/3149.3158
projectionNP-completenessBoolean functioncircuit complexitycomplexity theorycomplexity classesTuring-machine
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Complexity models for incremental computation, Threshold circuits of bounded depth, Threshold functions and bounded depth monotone circuits, The monotone circuit complexity of Boolean functions, Some results on uniform arithmetic circuit complexity, A reducibility concept for problems defined in terms of ordered binary decision diagrams, Feasible arithmetic computations: Valiant's hypothesis, There are no p-complete families of symmetric Boolean functions, Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\), On monotone simulations on nonmonotone networks, Weighted hypertree decompositions and optimal query plans, Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines, Gap-languages and log-time complexity classes, An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas, Logic vs. complexity theoretic properties of the graph accessibility problem for directed graphs of bounded degree, Polynomial size \(\Omega\)-branching programs and their computational power, On the algebraic complexity of some families of coloured Tutte polynomials, Properties that characterize LOGCFL, Separating the eraser Turing machine classes \(L_ e\), \(NL_ e\), \(co- NL_ e\) and \(P_ e\), Nonuniform complexity and the randomness of certain complete languages, The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems, Complete problems for monotone NP, Methods for proving completeness via logical reductions, Using the Hamiltonian path operator to capture NP, Hypertree decompositions and tractable queries, On pseudorandomness and resource-bounded measure, Lower bounds for the majority communication complexity of various graph accessibility problems, Dot operators, Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits, Completeness and non-completeness results with respect to read-once projections, Uniform Constraint Satisfaction Problems and Database Theory, A measure in which Boolean negation is exponentially powerful, Expressiveness of matchgates.
