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

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
Original language description
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
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
<a href="/en/project/EE2.3.30.0009" target="_blank" >EE2.3.30.0009: Employment of Newly Graduated Doctors of Science for Scientific Excellence</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)