Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

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
Presentation: Valyis.ppt.ppt
Slot: Tue, 11:30-11:50, Faraday C (col. 3)


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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by