1 Ocak 2013 Dergi makalesi Açık Erişim

Yakaryilmaz, Abuzer; Say, A. C. Cem

MARC21 XML

<?xml version='1.0' encoding='UTF-8'?>
<record xmlns="http://www.loc.gov/MARC21/slim">
  <leader>00000nam##2200000uu#4500</leader>
  <datafield tag="909" ind1="C" ind2="4">
    <subfield code="n">1</subfield>
    <subfield code="c">107-134</subfield>
    <subfield code="v">123</subfield>
    <subfield code="p">FUNDAMENTA INFORMATICAE</subfield>
  </datafield>
  <controlfield tag="005">20210315083102.0</controlfield>
  <datafield tag="909" ind1="C" ind2="O">
    <subfield code="o">oai:zenodo.org:15181</subfield>
    <subfield code="p">user-tubitak-destekli-proje-yayinlari</subfield>
  </datafield>
  <datafield tag="100" ind1=" " ind2=" ">
    <subfield code="u">Univ Latvia, Fac Comp, LV-1586 Riga, Latvia</subfield>
    <subfield code="a">Yakaryilmaz, Abuzer</subfield>
  </datafield>
  <datafield tag="520" ind1=" " ind2=" ">
    <subfield code="a">It is a widely believed, though unproven, conjecture that the capability of postselection increases the language recognition power of both probabilistic and quantum polynomial-time computers. It is also unknown whether polynomial-time quantum machines with postselection are more powerful than their probabilistic counterparts with the same resource restrictions. We approach these problems by imposing additional constraints on the resources to be used by the computer, and are able to prove for the first time that postselection does augment the computational power of both classical and quantum computers, and that quantum does outperform probabilistic in this context, under simultaneous time and space bounds in a certain range. We also look at postselected versions of space-bounded classes, as well as those corresponding to error-free and one-sided error recognition, and provide classical characterizations. It is shown that NL would equal RL if the randomized machines had the postselection capability.</subfield>
  </datafield>
  <datafield tag="542" ind1=" " ind2=" ">
    <subfield code="l">open</subfield>
  </datafield>
  <datafield tag="650" ind1="1" ind2="7">
    <subfield code="2">opendefinition.org</subfield>
    <subfield code="a">cc-by</subfield>
  </datafield>
  <datafield tag="540" ind1=" " ind2=" ">
    <subfield code="u">http://www.opendefinition.org/licenses/cc-by</subfield>
    <subfield code="a">Creative Commons Attribution</subfield>
  </datafield>
  <controlfield tag="001">15181</controlfield>
  <datafield tag="980" ind1=" " ind2=" ">
    <subfield code="a">publication</subfield>
    <subfield code="b">article</subfield>
  </datafield>
  <datafield tag="245" ind1=" " ind2=" ">
    <subfield code="a">Proving the Power of Postselection</subfield>
  </datafield>
  <datafield tag="260" ind1=" " ind2=" ">
    <subfield code="c">2013-01-01</subfield>
  </datafield>
  <datafield tag="980" ind1=" " ind2=" ">
    <subfield code="a">user-tubitak-destekli-proje-yayinlari</subfield>
  </datafield>
  <datafield tag="700" ind1=" " ind2=" ">
    <subfield code="u">Bogazici Univ, Dept Comp Engn, TR-34342 Istanbul, Turkey</subfield>
    <subfield code="a">Say, A. C. Cem</subfield>
  </datafield>
  <datafield tag="856" ind1="4" ind2=" ">
    <subfield code="u">https://aperta.ulakbim.gov.trrecord/15181/files/bib-80ea22f7-a63c-48e7-846e-396835d7b0c1.txt</subfield>
    <subfield code="s">111</subfield>
    <subfield code="z">md5:888f127c64bb5683d2101112641cfc3a</subfield>
  </datafield>
  <datafield tag="024" ind1=" " ind2=" ">
    <subfield code="a">10.3233/FI-2013-803</subfield>
    <subfield code="2">doi</subfield>
  </datafield>
</record>