Power from random strings

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/...

Full description

Saved in:
Bibliographic Details
Main Authors: Allender, E., Buhrman, H., Koucky, M., van Melkebeek, D., Ronneburger, D.
Format: Conference Proceeding
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Artificial intelligence
Circuits
Computer science
control theory
systems
Engineering profession
Exact sciences and technology
Lattices
Polynomials
Theoretical computing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 678
container_issue
container_start_page 669
container_title
container_volume
creator Allender, E.
Buhrman, H.
Koucky, M.
van Melkebeek, D.
Ronneburger, D.
description We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.
doi_str_mv 10.1109/SFCS.2002.1181992
format conference_proceeding
fullrecord <record><control><sourceid>pascalfrancis_6IE</sourceid><recordid>TN_cdi_ieee_primary_1181992</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>1181992</ieee_id><sourcerecordid>15618534</sourcerecordid><originalsourceid>FETCH-LOGICAL-i203t-c47d2a39d35cab52121055e45f045e6a246a3683a88d3dde0716e73c4707f3983</originalsourceid><addsrcrecordid>eNpFT8tKQzEUDKhgW_2A4qYbl7eenJOTx1IuVoVCC9V1iTeJRPoiKYh_74UruBqGeTAjxFTCXEpwD5tFu5kjAPbUSufwQozBaMfSIuKlGAEabFihvRbjWr8AFDDQSEzXx-9YZqkc97PiD6GHei758FlvxFXyuxpv_3Ai3hdPb-1Ls1w9v7aPyyYj0LnplAnoyQXizn8wSpTAHBUnUBy1R6U9aUve2kAhRDBSR0N9DEwiZ2ki7ofek6-d36V-RZfr9lTy3pefrWQtLZPqfXeDL8cY_-XhLv0CE45GOQ</addsrcrecordid><sourcetype>Index Database</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>Power from random strings</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Allender, E. ; Buhrman, H. ; Koucky, M. ; van Melkebeek, D. ; Ronneburger, D.</creator><creatorcontrib>Allender, E. ; Buhrman, H. ; Koucky, M. ; van Melkebeek, D. ; Ronneburger, D.</creatorcontrib><description>We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.</description><identifier>ISSN: 0272-5428</identifier><identifier>ISBN: 0769518222</identifier><identifier>ISBN: 9780769518220</identifier><identifier>DOI: 10.1109/SFCS.2002.1181992</identifier><language>eng</language><publisher>Los Alamitos CA: IEEE</publisher><subject>Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Artificial intelligence ; Circuits ; Computer science; control theory; systems ; Engineering profession ; Exact sciences and technology ; Lattices ; Polynomials ; Theoretical computing</subject><ispartof>Annual Symposium on Foundations of Computer Science, 2002, p.669-678</ispartof><rights>2004 INIST-CNRS</rights><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/1181992$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,4050,4051,27925,54555,54920,54932</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/1181992$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=15618534$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Allender, E.</creatorcontrib><creatorcontrib>Buhrman, H.</creatorcontrib><creatorcontrib>Koucky, M.</creatorcontrib><creatorcontrib>van Melkebeek, D.</creatorcontrib><creatorcontrib>Ronneburger, D.</creatorcontrib><title>Power from random strings</title><title>Annual Symposium on Foundations of Computer Science</title><addtitle>SFCS</addtitle><description>We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.</description><subject>Algorithmics. Computability. Computer arithmetics</subject><subject>Applied sciences</subject><subject>Artificial intelligence</subject><subject>Circuits</subject><subject>Computer science; control theory; systems</subject><subject>Engineering profession</subject><subject>Exact sciences and technology</subject><subject>Lattices</subject><subject>Polynomials</subject><subject>Theoretical computing</subject><issn>0272-5428</issn><isbn>0769518222</isbn><isbn>9780769518220</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>2002</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNpFT8tKQzEUDKhgW_2A4qYbl7eenJOTx1IuVoVCC9V1iTeJRPoiKYh_74UruBqGeTAjxFTCXEpwD5tFu5kjAPbUSufwQozBaMfSIuKlGAEabFihvRbjWr8AFDDQSEzXx-9YZqkc97PiD6GHei758FlvxFXyuxpv_3Ai3hdPb-1Ls1w9v7aPyyYj0LnplAnoyQXizn8wSpTAHBUnUBy1R6U9aUve2kAhRDBSR0N9DEwiZ2ki7ofek6-d36V-RZfr9lTy3pefrWQtLZPqfXeDL8cY_-XhLv0CE45GOQ</recordid><startdate>2002</startdate><enddate>2002</enddate><creator>Allender, E.</creator><creator>Buhrman, H.</creator><creator>Koucky, M.</creator><creator>van Melkebeek, D.</creator><creator>Ronneburger, D.</creator><general>IEEE</general><scope>6IE</scope><scope>6IH</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIO</scope><scope>IQODW</scope></search><sort><creationdate>2002</creationdate><title>Power from random strings</title><author>Allender, E. ; Buhrman, H. ; Koucky, M. ; van Melkebeek, D. ; Ronneburger, D.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i203t-c47d2a39d35cab52121055e45f045e6a246a3683a88d3dde0716e73c4707f3983</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>2002</creationdate><topic>Algorithmics. Computability. Computer arithmetics</topic><topic>Applied sciences</topic><topic>Artificial intelligence</topic><topic>Circuits</topic><topic>Computer science; control theory; systems</topic><topic>Engineering profession</topic><topic>Exact sciences and technology</topic><topic>Lattices</topic><topic>Polynomials</topic><topic>Theoretical computing</topic><toplevel>online_resources</toplevel><creatorcontrib>Allender, E.</creatorcontrib><creatorcontrib>Buhrman, H.</creatorcontrib><creatorcontrib>Koucky, M.</creatorcontrib><creatorcontrib>van Melkebeek, D.</creatorcontrib><creatorcontrib>Ronneburger, D.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan (POP) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEL</collection><collection>IEEE Proceedings Order Plans (POP) 1998-present</collection><collection>Pascal-Francis</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Allender, E.</au><au>Buhrman, H.</au><au>Koucky, M.</au><au>van Melkebeek, D.</au><au>Ronneburger, D.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Power from random strings</atitle><btitle>Annual Symposium on Foundations of Computer Science</btitle><stitle>SFCS</stitle><date>2002</date><risdate>2002</risdate><spage>669</spage><epage>678</epage><pages>669-678</pages><issn>0272-5428</issn><isbn>0769518222</isbn><isbn>9780769518220</isbn><abstract>We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.</abstract><cop>Los Alamitos CA</cop><pub>IEEE</pub><doi>10.1109/SFCS.2002.1181992</doi><tpages>10</tpages></addata></record>
fulltext fulltext_linktorsrc
identifier ISSN: 0272-5428
ispartof Annual Symposium on Foundations of Computer Science, 2002, p.669-678
issn 0272-5428
language eng
recordid cdi_ieee_primary_1181992
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Algorithmics. Computability. Computer arithmetics
Applied sciences
Artificial intelligence
Circuits
Computer science
control theory
systems
Engineering profession
Exact sciences and technology
Lattices
Polynomials
Theoretical computing
title Power from random strings
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-06T05%3A51%3A51IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-pascalfrancis_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Power%20from%20random%20strings&rft.btitle=Annual%20Symposium%20on%20Foundations%20of%20Computer%20Science&rft.au=Allender,%20E.&rft.date=2002&rft.spage=669&rft.epage=678&rft.pages=669-678&rft.issn=0272-5428&rft.isbn=0769518222&rft.isbn_list=9780769518220&rft_id=info:doi/10.1109/SFCS.2002.1181992&rft_dat=%3Cpascalfrancis_6IE%3E15618534%3C/pascalfrancis_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i203t-c47d2a39d35cab52121055e45f045e6a246a3683a88d3dde0716e73c4707f3983%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=1181992&rfr_iscdi=true