Logical Approaches to Computational Barriers

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 |

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 |