scientific article

zbMath0444.94037MaRDI QIDQ3888985

Larry J. Stockmeyer

Publication date: 1979

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

zbMATH Keywords

symmetric Boolean functionscombinational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (16)

On the complexity of theories of permutations ⋮ The complementation problem for Büchi automata with applications to temporal logic ⋮ The complexity of PDL with interleaving ⋮ Isomorphisms and 1-L reductions ⋮ The complexity of reasoning about knowledge and time. I: Lower bounds ⋮ A 3n-lower bound on the network complexity of Boolean functions ⋮ Complexity results for classes of quantificational formulas ⋮ Interval logics and their decision procedures. I: An interval logic ⋮ Asymptotical behaviour of some non-uniform measures ⋮ Practical decidability ⋮ On the equivalence, containment, and covering problems for the regular and context-free languages ⋮ The polynomial-time hierarchy ⋮ On the complexity of some two-person perfect-information games ⋮ Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete ⋮ The complexity of the satisfiability problem for Krom formulas ⋮ On classes of tractable unrestricted regular expressions

This page was built for publication: