Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Solving a PSPACE-complete problem by a linear interval-valued computation


Speaker: Sándor Vályi
Author(s): Benedek Nagy and Sándor Vályi
Slot: Array, 11:30-11:50, col. 3

Abstract

An interval-valued computing approach was presented in [Nagy, CiE2005]. The
computation is executed on interval-valued bytes, the bits of which 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. The question of which complexity
is needed to solve PSPACE-complete problems in this paradigm was also raised in
[Nagy, CiE2005]. An answer to this question is provided now, namely, we show
that the problem of validity of quantified propositional formulae is decidable
by a linear interval-valued computation.


websites: Arnold Beckmann 2006-04-28