On the polynomial computability of some rudimentary predicates. (Q1889506)

The author investigates polynomial computability of rudimentary predicates introduced by \textit{A. V. Kuznetsov} [``Canonical form theorem for ordinally recursive functions'', in: \textit{R. L. Goodstein}, Mathematical logic (Russian translation), Inostr. Lit., Moskva (1961)] and \textit{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\}\). \textit{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.