
PreviousNext
Suppose that $p$ is a prime number $A$ is a finite set
with $n$ elements
and for each sequence $a=<a_{1},...,a_{k}>$ of length $k$ from the
elements of
$A$, $x_{a}$ is a variable. (We may think that $k$ and $p$ are fixed an
$n$ is sufficiently large.) We will ...
more >>>
We present a Logspace, many-one reduction from the undirected
st-connectivity problem to its complement. This shows that
$SL=co-SL$
We study the computational complexity of languages which have
interactive proofs of logarithmic knowledge complexity. We show that
all such languages can be recognized in ${\cal BPP}^{\cal NP}$. Prior
to this work, for languages with greater-than-zero knowledge
complexity (and specifically, even for knowledge complexity 1) only
trivial computational complexity bounds ...
more >>>
PreviousNext