کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436472 | 690006 | 2008 | 15 صفحه PDF | دانلود رایگان |
At the conference CiE 2005, the first author introduced a new model for analog computations, namely interval-valued computations. In this model, computations work on the so-called interval-valued bytes, which are special subsets of the interval [0,1) rather than a finite sequence of bits. The question was posed there, which complexity is needed to solve -complete problems in this paradigm. In this paper, after formalizing the computational model, we answer this question. We show that the validity problem of quantified propositional formulae is decidable by a linear interval-valued computation. As a consequence, all polynomial space problems are decidable by a polynomial interval-valued computation. Furthermore, it is proven that coincides with the class of languages which are decidable by a restricted polynomial interval-valued computation.
Journal: Theoretical Computer Science - Volume 394, Issue 3, 8 April 2008, Pages 208-222