Solving a PSPACE-problem by a linear interval-valued computation
Loading...
Files
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We continue investigation of interval-valued computing based on
\cite{NB1} where computation is executed on interval-valued bytes
which are bits indexed by the interval [0,1] rather than by a
finite set. This device was presented there as a new possible
model of analogue computers. Also the question was posed in
\cite{NB1}, which complexity is needed to solve PSPACE-complete
problems in this paradigm. We answer this question. Namely, we
show that the problem of validity of quantified propositional
formulae is decidable by a linear interval-valued computation.