Reductions to the set of random strings: The resource-bounded case
This paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out in [Allender et al] to settle this conjecture cannot succeed without significant alteratio...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2014-08-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/723/pdf |
| _version_ | 1827322849967210496 |
|---|---|
| author | Eric Allender Harry Buhrman Luke Friedman Bruno Loff |
| author_facet | Eric Allender Harry Buhrman Luke Friedman Bruno Loff |
| author_sort | Eric Allender |
| collection | DOAJ |
| description | This paper is motivated by a conjecture that BPP can be characterized in
terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random
strings. In this paper we show that an approach laid out in [Allender et al] to
settle this conjecture cannot succeed without significant alteration, but that
it does bear fruit if we consider time-bounded Kolmogorov complexity instead.
We show that if a set A is reducible in polynomial time to the set of
time-t-bounded Kolmogorov random strings (for all large enough time bounds t),
then A is in P/poly, and that if in addition such a reduction exists for any
universal Turing machine one uses in the definition of Kolmogorov complexity,
then A is in PSPACE. |
| first_indexed | 2024-04-25T01:35:22Z |
| format | Article |
| id | doaj.art-466a7f61f6cd45faa1220c986ef2bcd5 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:22Z |
| publishDate | 2014-08-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-466a7f61f6cd45faa1220c986ef2bcd52024-03-08T09:37:13ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742014-08-01Volume 10, Issue 310.2168/LMCS-10(3:5)2014723Reductions to the set of random strings: The resource-bounded caseEric Allenderhttps://orcid.org/0000-0002-0650-028XHarry BuhrmanLuke FriedmanBruno Loffhttps://orcid.org/0000-0001-7562-457XThis paper is motivated by a conjecture that BPP can be characterized in terms of polynomial-time nonadaptive reductions to the set of Kolmogorov-random strings. In this paper we show that an approach laid out in [Allender et al] to settle this conjecture cannot succeed without significant alteration, but that it does bear fruit if we consider time-bounded Kolmogorov complexity instead. We show that if a set A is reducible in polynomial time to the set of time-t-bounded Kolmogorov random strings (for all large enough time bounds t), then A is in P/poly, and that if in addition such a reduction exists for any universal Turing machine one uses in the definition of Kolmogorov complexity, then A is in PSPACE.https://lmcs.episciences.org/723/pdfcomputer science - computational complexitycomputer science - logic in computer science |
| spellingShingle | Eric Allender Harry Buhrman Luke Friedman Bruno Loff Reductions to the set of random strings: The resource-bounded case Logical Methods in Computer Science computer science - computational complexity computer science - logic in computer science |
| title | Reductions to the set of random strings: The resource-bounded case |
| title_full | Reductions to the set of random strings: The resource-bounded case |
| title_fullStr | Reductions to the set of random strings: The resource-bounded case |
| title_full_unstemmed | Reductions to the set of random strings: The resource-bounded case |
| title_short | Reductions to the set of random strings: The resource-bounded case |
| title_sort | reductions to the set of random strings the resource bounded case |
| topic | computer science - computational complexity computer science - logic in computer science |
| url | https://lmcs.episciences.org/723/pdf |
| work_keys_str_mv | AT ericallender reductionstothesetofrandomstringstheresourceboundedcase AT harrybuhrman reductionstothesetofrandomstringstheresourceboundedcase AT lukefriedman reductionstothesetofrandomstringstheresourceboundedcase AT brunoloff reductionstothesetofrandomstringstheresourceboundedcase |