On the polynomial computability of some rudimentary predicates.

*(English. Russian original)*Zbl 1077.03023
Math. Notes 74, No. 1, 64-69 (2003); translation from Mat. Zametki 74, No. 1, 69-75 (2003).

The author investigates polynomial computability of rudimentary predicates introduced by A. V. Kuznetsov [“Canonical form theorem for ordinally recursive functions”, in: R. L. Goodstein, Mathematical logic (Russian translation), Inostr. Lit., Moskva (1961)] and R. M. Smullyan [Theory of formal systems, Princeton Univ. Press, Princeton, N.J. (1961; Zbl 0097.24503)]. In an earlier article [“On the complexity of computation of rudimentary predicates”, Discrete Math. Appl. 10, No. 6, 571–585 (2000); translation from Diskretn. Mat. 12, No. 4, 83–98 (2000; Zbl 1044.03026)] the author has proved that rudimentary \(\exists\)- and \(\forall\)-predicates can be computed deterministically in polynomial time. In the article under review the author proves Theorem 1 stating that any rudimentary predicate of the \(\exists \forall\)-class can be computed by a suitable deterministic algorithm in polynomial time. After that the author investigates the rudimentary predicates in prenex normal form with a special “length” restriction to the bounded variables: \((Q_{1}y_{1})_{| y_{1}| \leq | z_{1}| }\ldots (Q_{n}y_{n})_{| y_{n}| \leq | z_{n}| }(T=U)\), where \(Q_{i}\), \(1\leq i\leq n\) are \(\exists\)- or \(\forall\)-quantifiers and \(| a| \) denotes the binary length of the number \(a.\) \(T\) and \(U\) are string terms formed from the characters of variables and strings in the alphabeth \(\{1,2\}\). N. K. Kosovskij [Elements of mathematical logic and its applications to the theory of subrecursive algorithms (Russian), Leningrad Univ. Publ., Leningrad (1981; Zbl 0479.03001)] has shown that the class of these predicates coincides with the class of rudimentary predicates. (The proof of Theorem 1 also uses this fact). A rudimentary predicate \(\rho (a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n},c_{1},\ldots ,c_{r_{j}})\) representable in the above-mentioned form is said to be compact if for each of the variables \(y_{j}\) there exists a Skolem function \(f_{j}(x_{1},\ldots ,x_{m},z_{1},\ldots ,z_{n},y_{j1},\ldots ,y_{jr_{j}})\) such that if the tuples \((a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n},c_{1},\ldots ,c_{r_{j}})\), \((a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n},c_{1}^{\prime },\ldots ,c_{r_{j}}^{\prime })\) both belong to the domain of the function \(f_{j}\) and \(| c_{1}| =| c_{1}^{\prime }| ,\ldots ,| c_{r_{j}}| =| c_{r_{j}}^{\prime }| \) then
\[
| f_{j}(a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n},c_{1},\ldots ,c_{r_{j}})| = | f_{j}(a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n},| c_{1}^{\prime }| ,\ldots ,| c_{r_{j}}^{\prime }| )|.
\]
The author proves (Theorem 2) that any compact rudimentary predicate can be computed by a suitable deterministic algorithm in polynomial time.

Reviewer: Hrant B. Marandjian (Erevan)

##### MSC:

03D15 | Complexity of computation (including implicit computational complexity) |

03-02 | Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations |

68Q25 | Analysis of algorithms and problem complexity |