Transcript Valyis.p[..]

Solving a PSPACE-complete
problem by a linear intervalvalued computation
Benedek Nagy, Sándor Vályi
University of Debrecen, Faculty of
Informatics
Hungary
Introduction
• Definitions (interval-value, operations on
them, computations and decidability)
• Motivation
• Complexity results
• Proof I.
• Variations on the theme
• Proof II. (if time available)
Definitions
• Benedek Nagy: An interval-valued
computing device, in: “Computability in
Europe 2005: New computational paradigms”, ILLC Publications
• Interval-value: a subset of [0,1), union of
subintervals of form [a,b). Also are
representable by characteristic function.
• The set of allowed interval-values: V.
• One distinguished interval-value:
FIRSTHALF.
Example. An interval-value
FIRSTHALF
Operations on V:
•
Boolean operations, for subsets:
+ union, - complementation,
• Shifts (L,R),
[the above are analogous to the
operators on finite bytes],
• Product (*)
[Nagy’s dissertation, many-valued logic].
• Shift to the right
If no such component: does nothing
• Product
Example
for
product
operator
Interval-valued computation
sequence
A sequence of operator applications to
already constructed interval-values,
starting from FIRSTHALF.
• That is, <S(0), S(1),…, S(n)>, (n  IN),
• where S(0) = FIRSTHALF,
• for each i<n+1: S(i+1) = op(S(k), S(j)),
•
(op  {+,-,L,R,*}, k<i,j<i)
• (functional style, formalising the original
paper!)
The value ||L|| of an interval-valued
computation sequence:
• ||FIRSTHALF||= [0,1/2).
• The meaning of the operators are
described informally by the previous
figures (only in this talk, in paper: formal
definitions).
Decidability
• A language L is decidable by an intervalvalued computation iff there is an
algorithm A that for each input word w
constructs an appropriate computation
sequence with last element A(w) such that
• w  L if and only if ||A(w)|| is nonempty.
• Further, we consider in this case -L also
decidable. (Testing emptiness is also
allowed then.)
Complexity
• A language L is decidable by a linear
interval-valued computation iff there is a
positive constant c and there is a
logarithmic space algorithm A, that for
each input word w constructs an
appropriate computation sequence with
last element S(n) such that
• w  L if and only if || S(n) || is nonempty,
moreover, n does not exceed c|w|.
Theorem.
(question: referee of first paper)
There is a PSPACE-complete problem that is
decidable by a linear interval-valued
computation. 
• We prove it for one of the basic examples for
PSPACE-problems, namely, the problem of
validity of a quantified Boolean formula. (QSAT)
• In the paper submitted to this Conference we
have given a formal proof. In this talk illustration
only.
Illustration for the proof.
•
Illustration, Part 2.
Restriction on i-v computations
• A language L is said to be decidable by a restricted
polynomial size interval-valued computation iff
• There exists a polynom P and a logarithmic space
algorithm A with the following properties.
• For each input word w, A constructs a computation
sequence with last element S(n) such that
• w  L if and only if || S(n) || is nonempty,
• n does not exceed P(|w|), further,
• the left side of the product applications is always
•
FIRSTHALF.
Theorem 2. (after submitting)
• PSPACE coincides with the class of
languages decidable by a restricted
polynomial size interval-valued
computation.
In a technical report we have proved this formally.
We outline this proof, at the end of this talk.
If we release the condition on the left size of the operators, then we obtain
that the class of languages decidable by a polynomial interval-valued
computation is included in EXPSPACE. (equality?)
Motivation
• Analogous computation. New version, compared
to B—S—S,
• Fits into computation over algebraic structures,
• Analogous data representation by waves (1
dimension, this paper) is legitimate just as by
images (2 dimension, Naughton and Woods, CiE
2005) [also in Theoretical C.S.],
• Infinite Turing machine computations with dense
memory organisation .
Motivation for the operators
• Similarity to operators in digital computers
• Turing completeness
• Mathematically: The set of the allowed
values equipped with the operators is a
Boolean algebra with operators
The structure of interval-values with
these operators
• First-order theory of this structure, its metamathematical
properties.
• The closed terms of this structure (involving no variables,
only the constant FIRSTHALF): equality, inclusion is
decidable in exponential space.
• What if arbitrary terms?
• Monadic second-order theory of this structure: For
possible description of the class of languages decidable
by an arbitrary interval-valued computation.
• Combination with the forthcoming variations:
Variations on the theme, further
work:
• The allowed basic interval-values can be
varied:
• -- Finite unions of subintervals
• -- Arbitrary subsets
• -- Unions of shifts of [0,1/2n]
• All the questions remain interesting.
• Other operators should also be developed,
retaining Turing completeness. Esp. for
the second variation!
• Another natural ideas are the following ones:
• What happens if not an algorithm is responsible
for producing different computation sequences
for different input words, but an interval-valued
algorithm is a pair of a fixed computation
sequence and a “digital-analog converter” which
takes the input word and produces an intervalvalue – and the answer is taking by an “analogdigital converter”.
• Imperative paradigm for i-valued computation.
Work to do, not mentioned yet
• To show Turing completeness in a
mathematical manner, e.g. give a problem
in EXPSPACE\PSPACE solvable by a
non-restricted polynomial i-v computation,
• Investigate connections with interval
temporal logic.