About: Power from Random Strings     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

AttributesValues
rdf:type
Description
  • We show that sets consisting of strings of high Kolmogorov comlexity provide examples of sets that are complete for several complexity classes under probabilistic and nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let R_C be the set of strings x having comlexity at least |x|2, according to the usual Kolmogorov complexity measure C. We show that R_C is hard for the class of recursive functions under P/poly-truth-table reductions. Furthermore, we show that EXP is included in NP^{R_C}and PSPACE is in P^{R_C}. We also study resource bounded versions of Kolmogorov complexity and we show tighter results for the hardness and completeness of the sets of Kolmogorov random strings with respect to these measures.
  • We show that sets consisting of strings of high Kolmogorov comlexity provide examples of sets that are complete for several complexity classes under probabilistic and nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let R_C be the set of strings x having comlexity at least |x|2, according to the usual Kolmogorov complexity measure C. We show that R_C is hard for the class of recursive functions under P/poly-truth-table reductions. Furthermore, we show that EXP is included in NP^{R_C}and PSPACE is in P^{R_C}. We also study resource bounded versions of Kolmogorov complexity and we show tighter results for the hardness and completeness of the sets of Kolmogorov random strings with respect to these measures. (en)
  • Zkoumáme výpočetní sílu množiny Kolmogorovsky náhodných řetízků při použití jako orákulum. (cs)
Title
  • Power from Random Strings
  • Power from Random Strings (en)
  • Síla náhodných řetízků (cs)
skos:prefLabel
  • Power from Random Strings
  • Power from Random Strings (en)
  • Síla náhodných řetízků (cs)
skos:notation
  • RIV/67985840:_____/06:00038960!RIV07-AV0-67985840
http://linked.open.../vavai/riv/strany
  • 1467;1493
http://linked.open...avai/riv/aktivita
http://linked.open...avai/riv/aktivity
  • Z(AV0Z10190503)
http://linked.open...iv/cisloPeriodika
  • 6
http://linked.open...vai/riv/dodaniDat
http://linked.open...aciTvurceVysledku
http://linked.open.../riv/druhVysledku
http://linked.open...iv/duvernostUdaju
http://linked.open...titaPredkladatele
http://linked.open...dnocenehoVysledku
  • 493551
http://linked.open...ai/riv/idVysledku
  • RIV/67985840:_____/06:00038960
http://linked.open...riv/jazykVysledku
http://linked.open.../riv/klicovaSlova
  • Kolmogorov complexity; completeness; reductions (en)
http://linked.open.../riv/klicoveSlovo
http://linked.open...odStatuVydavatele
  • US - Spojené státy americké
http://linked.open...ontrolniKodProRIV
  • [9FD7174E367E]
http://linked.open...i/riv/nazevZdroje
  • Siam Journal on Computing
http://linked.open...in/vavai/riv/obor
http://linked.open...ichTvurcuVysledku
http://linked.open...cetTvurcuVysledku
http://linked.open...UplatneniVysledku
http://linked.open...v/svazekPeriodika
  • 35
http://linked.open...iv/tvurceVysledku
  • Koucký, Michal
  • Allender, E.
  • Ronneburger, D.
  • Buhrman, H.
  • van Melkebeek, D.
http://linked.open...n/vavai/riv/zamer
issn
  • 0097-5397
number of pages
is http://linked.open...avai/riv/vysledek of
Faceted Search & Find service v1.16.118 as of Jun 21 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 112 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software