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.STACS.2018.51
URN: urn:nbn:de:0030-drops-84938
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8493/
Go to the corresponding LIPIcs Volume Portal

Nies, André ; Stephan, Frank

Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations

pdf-format:
LIPIcs-STACS-2018-51.pdf (0.4 MB)

Abstract

An infinite bit sequence is called recursively random if no computable strategy betting along the sequence has unbounded capital. It is well-known that the property of recursive randomness is closed under computable permutations. We investigate analogous statements for randomness notions defined by betting strategies that are computable within resource bounds. Suppose that S is a polynomial time computable permutation of the set of strings over the unary alphabet (identified with the set of natural numbers). If the inverse of S is not polynomially bounded, it is not hard to build a polynomial time random bit sequence Z such that Z o S is not polynomial time random. So one
should only consider permutations S satisfying the extra condition
that the inverse is polynomially bounded. Now the closure depends on additional assumptions in complexity theory.

Our first main result, Theorem 4, shows that if BPP contains a superpolynomial deterministic time class, then polynomial time randomness is not preserved by some permutation S such that in fact both S and its inverse are in P. Our second result, Theorem 11, shows that polynomial space randomness is preserved by polynomial time permutations with polynomially bounded inverse, so if P = PSPACE then polynomial time randomness is preserved.

BibTeX - Entry

@InProceedings{nies_et_al:LIPIcs:2018:8493,
  author =	{Andr{\'e} Nies and Frank Stephan},
  title =	{{Closure of Resource-Bounded Randomness Notions Under Polynomial-Time Permutations}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{51:1--51:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Rolf Niedermeier and Brigitte Vall{\'e}e},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8493},
  URN =		{urn:nbn:de:0030-drops-84938},
  doi =		{10.4230/LIPIcs.STACS.2018.51},
  annote =	{Keywords: Computational complexity, Randomness via resource-bounded betting strategies, Martingales, Closure under permutations}
}

Keywords: Computational complexity, Randomness via resource-bounded betting strategies, Martingales, Closure under permutations
Collection: 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Issue Date: 2018
Date of publication: 27.02.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI