Classifying the computational complexity of problems
L Stockmeyer - The journal of symbolic logic, 1987 - cambridge.org
One of the more significant achievements of twentieth century mathematics, especially from
the viewpoints of logic and computer science, was the work of Church, Gödel and Turing in …
the viewpoints of logic and computer science, was the work of Church, Gödel and Turing in …
[PDF][PDF] Matching is as easy as matrix inversion
K Mulmuley, UV Vazirani, VV Vazirani - Proceedings of the nineteenth …, 1987 - dl.acm.org
A new algorithm for finding a maximum matching in a general graph is presented; its special
feature being that the only computationally non-trivial step required in its execution is the …
feature being that the only computationally non-trivial step required in its execution is the …
[PDF][PDF] The Boolean formula value problem is in ALOGTIME
SR Buss - Proceedings of the nineteenth annual ACM symposium …, 1987 - dl.acm.org
The Boolean formula value problem is to determine the truth value of a variable-free
Boolean formula, or equivalently, to recognize the true Boolean sentences. N. Lynch [ll] gave …
Boolean formula, or equivalently, to recognize the true Boolean sentences. N. Lynch [ll] gave …
Problems complete for deterministic logarithmic space
SA Cook, P McKenzie - Journal of Algorithms, 1987 - Elsevier
We exhibit several problems complete for deterministic logarithmic space under NC 1 (ie,
log depth) reducibility. The list includes breadth-first search and depth-first search of an …
log depth) reducibility. The list includes breadth-first search and depth-first search of an …
Properties that characterize LOGCFL
H Venkateswaran - Proceedings of the nineteenth annual ACM …, 1987 - dl.acm.org
Two properties, called semi-unboundedness, and polynomial proof-size, are identified as
key properties shared by the definitions of LOGCFL on several models of computations. The …
key properties shared by the definitions of LOGCFL on several models of computations. The …
A random NC algorithm for depth first search
A Aggarwal, R Anderson - Proceedings of the nineteenth annual ACM …, 1987 - dl.acm.org
In this paper we present a fast parallel algorithm for constructing a depth first search tree for
an undirected graph. The algorithm is an RNC algorithm, meaning that it is a probabilistic …
an undirected graph. The algorithm is an RNC algorithm, meaning that it is a probabilistic …
The matching problem for bipartite graphs with polynomially bounded permanents is in NC
DY Grigoriev, M Karpinski - 28th Annual Symposium on …, 1987 - ieeexplore.ieee.org
It is shown that the problem of deciding and constructing a perfect matching in bipartite
graphs G with the polynomial permanents of their n× n adjacency matrices A (perm (A)= nO …
graphs G with the polynomial permanents of their n× n adjacency matrices A (perm (A)= nO …
[图书][B] Parallel complexity theory
I Parberry - 1987 - dl.acm.org
Parallel complexity theory | Guide books skip to main content ACM Digital Library home
ACM home Google, Inc. (search) Advanced Search Browse About Sign in Register …
ACM home Google, Inc. (search) Advanced Search Browse About Sign in Register …
[图书][B] Expressibility as a complexity measure: results and directions
N Immerman - 1987 - ieeexplore.ieee.org
Given a property, S, one can discuss the computational complexity of checking whether or
not an input satisfies S. One can also ask," What is the complexity of expressing the property …
not an input satisfies S. One can also ask," What is the complexity of expressing the property …
Fast parallel algorithms for chordal graphs
We present an NC algorithm for recognizing chordal graphs, and we present NC algorithms
for finding the following objects on chordal graphs: all maximal cliques, an intersection …
for finding the following objects on chordal graphs: all maximal cliques, an intersection …