A Characterization of NP Within Interval-Valued Computing
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer-Verlag Berlin
Access Rights
info:eu-repo/semantics/closedAccess
Abstract
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.
Description
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
Journal or Series
Machines, Computations, and Universality, Mcu 2015
WoS Q Value
Scopus Q Value
Volume
9288
