{"entities":{"Q1889506":{"pageid":1900248,"ns":120,"title":"Item:Q1889506","lastrevid":69205854,"modified":"2026-04-13T05:28:03Z","type":"item","id":"Q1889506","labels":{"en":{"language":"en","value":"On the polynomial computability of some rudimentary predicates."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2121013"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889506$BFC9108D-9A68-4AFB-856D-3554349A2945","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c65aeb9c360af82c218b8668751af59e954be760","datavalue":{"value":{"text":"On the polynomial computability of some rudimentary predicates.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1889506$04F4E0DF-369B-4C9A-B7D6-FEE82066B0DE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9450b5c06e25a5e1c8631adab9a3491bc633da48","datavalue":{"value":"1077.03023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889506$90F5DBA2-B129-4B09-B01E-F9613662375F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"55a68c3afc124436d74e599f959ee71809471f42","datavalue":{"value":"10.1023/A:1025067132637","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889506$BBE9BC91-20CD-4A16-9DE2-0EB7313F4903","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"00de3e6b6cfff0576fe0e1d6bc63c05579d2cb43","datavalue":{"value":{"entity-type":"item","numeric-id":173953,"id":"Q173953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889506$1B281D9B-BD65-42B5-8F2B-28D901DE44B5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4026df8c189dcb55f8519aced96bbb663b5d400a","datavalue":{"value":{"time":"+2004-12-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1889506$EFB53CCD-CCA5-43ED-A0D3-D5DEF81F4891","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c919bf8db0f0e43b6d72e82d0a97a95d6da034da","datavalue":{"value":"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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889506$B7A3F646-C22E-4C69-A446-5425A85322FD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889506$7C3A1089-FD61-44AD-8AD9-F4D07B116959","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"89663cdc2c9f64b2cd0a104bcac86329d89b9b2d","datavalue":{"value":"03-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889506$66F9D191-1EAB-4AB2-97E1-102EF27176F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889506$C7DEBF3B-226F-489F-9ECE-B6020B3CE493","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"63434a1907959107d894a137c50af191c9c379d7","datavalue":{"value":"2121013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889506$4E3A2CC3-25C6-40AA-A970-4ABC2CABF96F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889506$0FB64C7B-98DF-4D54-8F44-90A62A664C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fdc5f36893e170a997246adb218ecc59dab440c3","datavalue":{"value":"polynomial computability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889506$724A313D-04E2-4717-A06D-78CB0BE3E62A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"280933c389d95f4603ba2d739329fb8e9d5bfca9","datavalue":{"value":"prenex normal form","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889506$37CA165D-367F-421F-84D1-C7A2BB774419","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e47754ffe9f8f72760c9538dfd6b3c9b7ab6dc2c","datavalue":{"value":"rudimentary predicates","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889506$F22FA457-B0DE-4A5D-A37A-51805DD8BE38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93c047fb19c5161b32c5245d5c8c28b4500157fe","datavalue":{"value":"propositional logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1889506$A21EA767-BF01-4EEC-B2A7-28F72BD5177D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c4a95f085b4acb7c793008f4f9d663da3cb59bf","datavalue":{"value":{"entity-type":"item","numeric-id":314212,"id":"Q314212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889506$E2BEE5CD-6C5F-4D3B-BDCB-F0FF3B285E63","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fe64c30036b6931dfc08c246a2592bfd800c1f57","datavalue":{"value":{"entity-type":"item","numeric-id":1612485,"id":"Q1612485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889506$1FA505F9-E7A7-4DE9-A50F-157FAB135D1A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1889506$2498ED4D-410A-42F9-8377-44347735A116","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b7fdb715f43ae456dd88aca219f85ee99409508","datavalue":{"value":"https://doi.org/10.1023/a:1025067132637","type":"string"},"datatype":"url"},"type":"statement","id":"Q1889506$8D2C809D-C2F0-4EE7-B414-F299B9F9812F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"671d6c8aaa7b35b55212174b2995cea1dbb4daaa","datavalue":{"value":"W117604700","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1889506$8B8EDA35-DDA0-4FCA-8F04-956799B5818B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbbb79cd512d5b3cabb96d86f48bc3ec2154cad7","datavalue":{"value":{"entity-type":"item","numeric-id":4809504,"id":"Q4809504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce4db02aa74f46607e6e3aa0517cd9097da0edaf","datavalue":{"value":{"amount":"+0.9128098487854004","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889506$C908EDD2-EBA1-466B-ADA2-B6FFC78100F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e24ace4beec00e5225e1f25a1c57427ea356047","datavalue":{"value":{"entity-type":"item","numeric-id":3728887,"id":"Q3728887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98d319c8d40478d6467a4578b6b6b71136bcba2b","datavalue":{"value":{"amount":"+0.7885140776634216","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889506$D6B9A349-C787-47A8-9985-4514F02D6B69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b4da257adfa3098e146111db07027c7417c2813","datavalue":{"value":{"entity-type":"item","numeric-id":4731176,"id":"Q4731176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"269f608c64da09d0f1a33b6d63ebbe97e4ff1149","datavalue":{"value":{"amount":"+0.7554751038551331","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889506$F1618A14-D66F-4402-A3D3-BD70E31F770D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55908794973f088270d2386d3df32b90aba9f4dd","datavalue":{"value":{"entity-type":"item","numeric-id":1127532,"id":"Q1127532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3897dc353665e59a99ed7a1dddbe35e513ffec2a","datavalue":{"value":{"amount":"+0.7441375851631165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889506$8A88D5D9-E3B1-40AE-8A94-C12D524BD07F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d1056e844d1ad203927bcf7119fa2cfd081bb5e","datavalue":{"value":{"entity-type":"item","numeric-id":3148488,"id":"Q3148488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff3c8f5ecab409c494f9c2e6844bbcb1169a2fb4","datavalue":{"value":{"amount":"+0.737057626247406","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1889506$020A12E6-E9B7-4767-95AF-91FDC96DC1C1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the polynomial computability of some rudimentary predicates.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_polynomial_computability_of_some_rudimentary_predicates."}}}}}