Recognizability versus solvability of promise problems in finite, classical and quantum 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 of the public key cryptography. In the present paper a variety of issues is explored concerning dealing with the promise problems on the level of finite, classical, quantum and also semi-quantum 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 in the case the promise is simple (say regular), its disjoint subsets for so called yes and no cases do not have to be so. In addition, some results concerning descriptional complexity impacts on outcomes of some operations on promise problems are shown as well as the significant power of quantum versions of classical automata is demonstrated when dealing with some promise problems.