scientific article; zbMATH DE number 3555903
From MaRDI portal
Publication:4128417
zbMath0356.94042MaRDI QIDQ4128417
Publication date: 1977
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
An introduction to parallelism in combinatorial optimization ⋮ On the construction of parallel computers from various basis of Boolean functions ⋮ A theory of strict P-completeness ⋮ On the computational complexity of graph closures ⋮ Parallelism and the maximal path problem ⋮ The word and generator problems for lattices ⋮ How easy is local search? ⋮ The complexity of membership problems for circuits over sets of integers ⋮ Parallel evaluation of arithmetic circuits ⋮ Parallelism and the feedback vertex set problem ⋮ The complexity of intersecting finite automata having few final states ⋮ The logarithmic alternation hierarchy collapses: \(A\Sigma _ 2^{{\mathcal L}}=A\Pi_ 2^{{\mathcal L}}\) ⋮ Games for active XML revisited ⋮ The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem ⋮ On computing graph closures ⋮ Graph isomorphism, color refinement, and compactness ⋮ Balancing bounded treewidth circuits ⋮ A space efficient algorithm for the monotone planar circuit value problem ⋮ On the Structure of Solution-Graphs for Boolean Formulas ⋮ A simple P-complete problem and its language-theoretic representations ⋮ The complexity gap in the static analysis of cache accesses grows if procedure calls are added ⋮ Embedding arbitrary Boolean circuits into fungal automata ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem ⋮ A recognition and parsing algorithm for arbitrary conjunctive grammars. ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible ⋮ On the complexity of the stability problem of binary freezing totalistic cellular automata ⋮ The binary network flow problem is logspace complete for P ⋮ A P-complete graph partition problem ⋮ Number of quantifiers is better than number of tape cells ⋮ The maximum flow problem is log space complete for P ⋮ The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions ⋮ The complexity of short two-person games ⋮ On short paths interdiction problems: Total and node-wise limited interdiction ⋮ Properties that characterize LOGCFL ⋮ \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems ⋮ Oracle branching programs and Logspace versus \(P^*\) ⋮ The correlation between the complexities of the nonhierarchical and hierarchical versions of graph problems ⋮ The complexity of synchronizing Markov decision processes ⋮ On the computational complexity of data flow analysis over finite bounded meet semilattices ⋮ The complexity of circuit value and network stability ⋮ Isomorphism of Regular Trees and Words ⋮ TANTRIX\(^{\text{TM}}\) rotation puzzles are intractable ⋮ The complexity of agent design problems: Determinism and history dependence ⋮ Two dynamic programming algorithms for which interpreted pebbling helps ⋮ Ordered vertex removal and subgraph problems ⋮ Formal languages over GF(2) ⋮ On the complexity of asynchronous freezing cellular automata ⋮ The Monotone Circuit Value Problem with Bounded Genus Is in NC ⋮ Matchstick puzzles on a grid ⋮ A theory of strict P-completeness ⋮ Positive versions of polynomial time ⋮ The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions ⋮ Model Checking and Validity in Propositional and Modal Inclusion Logics ⋮ Module checking ⋮ Finding the closed partition of a planar graph
