Solving a PSPACE-problem by a linear interval-valued computation

Loading...
Thumbnail Image

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.

Description

Citation

Endorsement

Review

Supplemented By

Referenced By