Interval-valued computation

Interval computers are a special kind of theoretical models for computation that are capable of working on "interval-valued bytes": special subsets of the (0, 1) real interval. Thus, they can be regarded as kind of ideal analog computers. There are no architectures for their physical implementations. Such a model of computation is capable of solving NP-complete problems like tripartite matching.^[1] “The validity problem of quantified propositional formulae is decidable by a linear interval-valued computation. As a consequence, all polynomial space problems are decidable by a polynomial interval-valued computation. Furthermore, it is proven that PSPACE coincides with the class of languages which are decidable by a restricted polynomial interval-valued computation” (links added).^[2]

See also

• Real computation

Notes

1. Tajti & Nagy 2008
2. Nagy & Vályi 2008

References

• Tajti, Ákos (June 20, 2008). Solving Tripartite Matching by Interval-valued Computation in Polynomial Time. Computability in Europe 2008. Logic and Theory of Algorithms. pp. 208–222. {{cite conference}}: External link in |conferenceurl= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help); Unknown parameter |conferenceurl= ignored (|conference-url= suggested) (help) See short abstract.
• Nagy, Benedek (April 8, 2008). "Interval-valued computations and their connection with PSPACE". Theoretical Computer Science (Preface: From Gödel to Einstein: Computability between Logic and Physics). 394 (3): 208–222. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)