# zbMATH — the first resource for mathematics

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.
##### 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
Full Text: