License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.5
URN: urn:nbn:de:0030-drops-75297
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7529/
van Melkebeek, Dieter ;
Prakriya, Gautam
Derandomizing Isolation in Space-Bounded Settings
Abstract
We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance on shallow semi-unbounded circuits.
A common approach employs small weight assignments that make the solution of minimum weight unique. The Isolation Lemma and other known procedures use Omega(n) random bits to generate weights of individual bitlength O(log(n)). We develop a derandomized version for both settings that uses O(log(n)^{3/2}) random bits and produces weights of bitlength O(log(n)^{3/2}) in logarithmic space. The construction allows us to show that every language in NL can be accepted by a nondeterministic machine that runs in polynomial time and O(log(n)^{3/2}) space, and has at most one accepting computation path on every input. Similarly, every language in LogCFL can be accepted by a nondeterministic machine equipped with a stack that does not count towards the space bound, that runs in polynomial time and O(log(n)^{3/2}) space, and has at most one accepting computation path on every input.
We also show that the existence of somewhat more restricted isolations for reachability on digraphs implies that NL can be decided in logspace with polynomial advice. A similar result holds for certifying acceptance on shallow semi-unbounded circuits and LogCFL.
BibTeX - Entry
@InProceedings{vanmelkebeek_et_al:LIPIcs:2017:7529,
author = {Dieter van Melkebeek and Gautam Prakriya},
title = {{Derandomizing Isolation in Space-Bounded Settings}},
booktitle = {32nd Computational Complexity Conference (CCC 2017)},
pages = {5:1--5:32},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-040-8},
ISSN = {1868-8969},
year = {2017},
volume = {79},
editor = {Ryan O'Donnell},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7529},
URN = {urn:nbn:de:0030-drops-75297},
doi = {10.4230/LIPIcs.CCC.2017.5},
annote = {Keywords: Isolation lemma, derandomization, unambiguous nondeterminism, graph reachability, circuit certification}
}
|
Keywords: |
|
Isolation lemma, derandomization, unambiguous nondeterminism, graph reachability, circuit certification |
|
Collection: |
|
32nd Computational Complexity Conference (CCC 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.08.2017 |
