TY - GEN

T1 - Probabilistic log-space reductions and problems probabilistically hard for p

AU - Kirousis, Lefteris M.

AU - Spirakis, Paul

N1 - Publisher Copyright:
© 1988, Springer-Verlag.

PY - 1988

Y1 - 1988

N2 - We present in this paper an interesting kind of reductions and its variations (the probabilistic NC reductions) which allow us to argue about the parallel complexity of problems not easily shown to be complete for P. We show that a problem complete under these reductions cannot be in NC unless P c RNC. Based on these reductions we also show the P-completeness of a probabilistic problem, namely, given a dag for some nodes of which exactly one of the incoming edges fail (all incoming edges to such a node have equal probability to fail) approximate, within an arbitrary given absolute performance ratio the longest distance we can travel, with certainty, along the edges of the dag. In order to show the above result we show the P-completeness of the problem of approximating, with a given absolute performance ratio, the depth at which the ones arrive in a boolean monotone circuit.

AB - We present in this paper an interesting kind of reductions and its variations (the probabilistic NC reductions) which allow us to argue about the parallel complexity of problems not easily shown to be complete for P. We show that a problem complete under these reductions cannot be in NC unless P c RNC. Based on these reductions we also show the P-completeness of a probabilistic problem, namely, given a dag for some nodes of which exactly one of the incoming edges fail (all incoming edges to such a node have equal probability to fail) approximate, within an arbitrary given absolute performance ratio the longest distance we can travel, with certainty, along the edges of the dag. In order to show the above result we show the P-completeness of the problem of approximating, with a given absolute performance ratio, the depth at which the ones arrive in a boolean monotone circuit.

UR - http://www.scopus.com/inward/record.url?scp=85032225420&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032225420&partnerID=8YFLogxK

U2 - 10.1007/3-540-19487-8_19

DO - 10.1007/3-540-19487-8_19

M3 - Conference contribution

AN - SCOPUS:85032225420

SN - 9783540194873

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 163

EP - 175

BT - SWAT 88 - 1st Scandinavian Workshop on Algorithm Theory, Proceedings

A2 - Karlsson, Rolf

A2 - Lingas, Andrzej

PB - Springer Verlag

T2 - 1st Scandinavian Workshop on Algorithm Theory, SWAT 1988

Y2 - 5 July 1988 through 8 July 1988

ER -