Recognizability versus solvability of promise problems in classical and quantum finite automata framework
Jozef Gruska, Lvzhou Li, Shenggen Zheng · arXiv (Cornell University) · 2014
In pioneering papers \cite{ESY84,Gh06}, the concept of the {\em promise problems} was introduced and started to be systematically explored. It has been argued that promise problems should be seen as partial {\em decision problems} and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory issues explorations. Moreover, both of the above papers explored and summarized \cite{Gh06}, in some depth and systematically, promise problems in the context of the theory of the main computational complexity classes as well as in the context of cracking out the public key cryptography. In the present paper a variety of issues is explored concerning promise problems on the level of classical, quantum and also semi-quantum finite automata. Two acceptance modes, {\em recognizability} and {\em solvability} are introduced and their basic properties are explored. This is also to capture and explore the case that even if a promise is simple (say regular), its disjoint subsets, for so called yes and no cases, do not have to be so. In addition, several results concerning descriptional complexity impacts on outcomes of some operations on promise problems are shown and the increasing power of quantum versus classical automata is demonstrated when dealing with some promise problems.