Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2017

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: new computing paradigms

Sortuj według:

Ogranicz wyniki do:

A Shift-free Characterization of NP within Interval-valued Computing

Nagy B., Vályi S.

Fundamenta Informaticae

2017

Vol. 155, nr 1/2

187--207

Interval-valued computing is a new computing paradigm that is based on manipulations of interval-values. Interval-values are finite unions of intervals on the unit interval [0; 1) so this kind of computing can be considered as a continuous space machine like optical computing [25]. Based on the massive parallelism of this paradigm, various intractable problems can be solved efficiently, i.e., by polynomial number of steps. In this paper, the well-known complexity classes, NP and coNP are addressed. A specific subclass of polynomial size interval-valued computations is proven to characterize NP, that is, exactly languages with non-deterministically polynomial time complexity can be decided by interval-valued computations of this subclass. This specific subclass of interval-valued computations does not use any of the shift operators, moreover the product operator is used only in the starting section of the computation. Due to the fact that interval-valued computing is a deterministic model of computing, an analogue result can be established for the class coNP.