A Characterization of NP Within Interval-Valued Computing - Nagy, Benedek; Valyi, Sandor (Springer-Verlag Berlin, 2015)
In this paper, a syntactic subclass of polynomial size intervalvalued computations is given that characterizes NP, that is, exactly languages with non-deterministically polynomial time complexity can be decided by interval-valued computations of this subclass. This subclass refrains from using product and shift operators aside from a starting section of the computation.
7th International Conference on Machines, Computations and Universality (MCU) -- SEP 09-11, 2015 -- Famagusta, CYPRUS
Keywords: Unconventional computing; Interval-valued computing; Complexity; NP; coNP; Deterministic computing