Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F15%3A00084456" target="_blank" >RIV/00216224:14330/15:00084456 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.sciencedirect.com/science/article/pii/S0890540115000140" target="_blank" >http://www.sciencedirect.com/science/article/pii/S0890540115000140</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ic.2015.02.003" target="_blank" >10.1016/j.ic.2015.02.003</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

Popis výsledku v původním jazyce

Interactive proof systems (IP) are very powerful - languages they can accept form exactly PSPACE. They represent also one of the very fundamental concepts of theoretical computing and a model of computation by interactions. One of the key players in IP is verifier. In the original model of IP whose power is that of PSPACE, the only restriction on verifiers is that they work in randomized polynomial time. Because of such key importance of IP, it is of large interest to find out how powerful will IP be when verifiers are more restricted. So far this was explored for the case that verifiers are two-way probabilistic finite automata (Dwork and Stockmeyer, 1990) and one-way quantum finite automata as well as two-way quantum finite automata (Nishimura and Yamakami, 2009). IP in which verifiers use public randomization is called Arthur-Merlin proof systems (AM). AM with verifiers modeled by Turing Machines augmented with a fixed-size quantum register (qAM) were studied also by Yakaryilmaz (20

Název v anglickém jazyce

Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

Popis výsledku anglicky

Interactive proof systems (IP) are very powerful - languages they can accept form exactly PSPACE. They represent also one of the very fundamental concepts of theoretical computing and a model of computation by interactions. One of the key players in IP is verifier. In the original model of IP whose power is that of PSPACE, the only restriction on verifiers is that they work in randomized polynomial time. Because of such key importance of IP, it is of large interest to find out how powerful will IP be when verifiers are more restricted. So far this was explored for the case that verifiers are two-way probabilistic finite automata (Dwork and Stockmeyer, 1990) and one-way quantum finite automata as well as two-way quantum finite automata (Nishimura and Yamakami, 2009). IP in which verifiers use public randomization is called Arthur-Merlin proof systems (AM). AM with verifiers modeled by Turing Machines augmented with a fixed-size quantum register (qAM) were studied also by Yakaryilmaz (20

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Zaměstnáním čerstvých absolventů doktorského studia k vědecké excelenci</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2015

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Information and computation

ISSN

0890-5401

e-ISSN

—

Svazek periodika

241

Číslo periodika v rámci svazku

April 2015

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

197-214

Kód UT WoS článku

000353352800009

EID výsledku v databázi Scopus

—