Probabilistic log-space reductions and problems probabilistically hard for p

Lefteris M. Kirousis, Paul Spirakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSWAT 88 - 1st Scandinavian Workshop on Algorithm Theory, Proceedings
EditorsRolf Karlsson, Andrzej Lingas
PublisherSpringer Verlag
Pages163-175
Number of pages13
ISBN (Print)9783540194873
DOIs
StatePublished - 1988
Event1st Scandinavian Workshop on Algorithm Theory, SWAT 1988 - Halmstad, Sweden
Duration: Jul 5 1988Jul 8 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume318 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st Scandinavian Workshop on Algorithm Theory, SWAT 1988
Country/TerritorySweden
CityHalmstad
Period7/5/887/8/88

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Probabilistic log-space reductions and problems probabilistically hard for p'. Together they form a unique fingerprint.

Cite this