{"entities":{"Q1177041":{"pageid":1187790,"ns":120,"title":"Item:Q1177041","lastrevid":70168626,"modified":"2026-04-13T12:54:49Z","type":"item","id":"Q1177041","labels":{"en":{"language":"en","value":"Bounded arithmetic and the polynomial hierarchy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 12856"}},"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":"Q1177041$007506F5-FDB1-4CCA-AFDC-AD55A3C008FC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"18acf5d212d3e0bd0ddcf164f47efb091be42be2","datavalue":{"value":{"text":"Bounded arithmetic and the polynomial hierarchy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1177041$A8915DD7-048F-47E9-B718-977A0B82BD7C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"630ab074e1bdc246f59a846f35948e1310c9e451","datavalue":{"value":"0736.03022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177041$2ECC055A-6E04-44A5-9681-3C0C0CB01223","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3dd3a1bd03d5fe6fd51a94d120dfb579618fceb1","datavalue":{"value":"10.1016/0168-0072(91)90043-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177041$67FD489C-413B-4474-BE3B-17E830BAE92C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4b9ae896fbf78b3fa2084fd5300754d74076f66","datavalue":{"value":{"entity-type":"item","numeric-id":226860,"id":"Q226860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$B9B1D1D8-381B-4CD2-BBDE-54F77F1BD31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"318018faae3560d6874b4d183002bf8aee67c872","datavalue":{"value":{"entity-type":"item","numeric-id":185618,"id":"Q185618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$B469AB1F-A9F5-4A64-998F-762C9AEC3017","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"057136d60f841fac35f8dec23b81e4925462b1bc","datavalue":{"value":{"entity-type":"item","numeric-id":768306,"id":"Q768306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$931AF609-42B3-4206-A2B4-4B153C164532","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f91a4bcbc93435aed71775d25a4c5cd09e26f12d","datavalue":{"value":{"entity-type":"item","numeric-id":122505,"id":"Q122505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$38BD7451-33BC-4C93-8442-899CD0E64C90","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1177041$568C07CF-D694-4C20-930A-E75090936D54","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"473ee60549cc4c60b0654c235f1be316a2bdbc5f","datavalue":{"value":"The authors assume familarity with the book of \\textit{S. Buss} [Bounded arithmetic (1986; Zbl 0649.03042)]. They show that (1) \\(T_ 2^ i=S_ 2^{i+1}\\) implies \\(\\Sigma^ p_{i+1}\\subseteq\\Delta^ p_{i+1}/\\text{poly}\\). (For this result they use a Herbrand-type witnessing theorem for \\(\\exists\\forall\\exists\\Pi^ b_ i\\)-formulas provable in \\(T^ i_ 2\\), where the witnessing functions are in \\(\\square^ p_{i+1}\\)). (2) \\(S_ 2(\\alpha)\\) and \\(I\\Delta_ 0(f)\\) are not finitely axiomatizable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177041$BE4583F1-FA43-426B-AFE2-F82B57621430","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"59699d8ba436c4690eab2e3c0ee0a7ef0d967cec","datavalue":{"value":{"entity-type":"item","numeric-id":1177040,"id":"Q1177040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$CD31BD8F-EFB2-4E7C-BC5A-CE701E82A12C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177041$D5B14E6A-6BAD-4CD8-AAEB-BD103D10B755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177041$45AA4A37-6C7C-490A-B54A-E5BDEEABF50A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"08520ca024cbdd02ab63e9a013ea52433c010341","datavalue":{"value":"12856","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177041$AD70B9F1-8BA4-4C30-BC5C-FA92B59510A5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c0e656c5f8b69339fc940c4eb3f156e08d9f2ad","datavalue":{"value":"Herbrand-type witnessing theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1177041$2F305887-C0AF-4BFD-BF64-C1C580CE6EFF","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c7a44f79429805b508c0df9afd14c80f194c9597","datavalue":{"value":"Q106785050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177041$78263377-5DC0-4CF0-8BC9-88D3099EF0BD","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":"Q1177041$21C61CF8-6B0A-4A71-826C-F5431DE6891A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c4b58f9e8478a4210509de111b81e4ccd911506","datavalue":{"value":{"entity-type":"item","numeric-id":4086709,"id":"Q4086709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$268E4413-C8AE-4FC7-AED8-D21366AFEDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"035feb3d68e7fcb8cc1f5afc2267fb8cc293e0bf","datavalue":{"value":{"entity-type":"item","numeric-id":3794177,"id":"Q3794177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$F65FFFEE-8343-4B46-8D79-CA4C604536B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34a549ed1d776396be3e4308655e166de224ba89","datavalue":{"value":{"entity-type":"item","numeric-id":4133141,"id":"Q4133141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$BB355235-1E53-44AF-AD6F-7A5010E60E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"60bde2c1667b403bd07f99472a13c7986b2f5411","datavalue":{"value":{"entity-type":"item","numeric-id":3472099,"id":"Q3472099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$46BAB4C4-43BB-4FA5-A449-BF4CAE1DF495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d93c0216bb7a2404c766e146541a6f49efebe1b2","datavalue":{"value":{"entity-type":"item","numeric-id":1104318,"id":"Q1104318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$48A4E697-3573-4E99-894F-4422A2684177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3b936472256c474ab8250b72e7c010873198894","datavalue":{"value":{"entity-type":"item","numeric-id":4206725,"id":"Q4206725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$891D287F-ED3E-44F7-864D-C65609B29596","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3652d520789475601e366029ce7b257ab62a1ec7","datavalue":{"value":{"entity-type":"item","numeric-id":5905909,"id":"Q5905909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1177041$340E66B5-1B41-423F-91BB-9B1CDE9AD0D7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b0b9a4d1a7356b90c2510b1b7aff2cbc00ff4c9","datavalue":{"value":"https://doi.org/10.1016/0168-0072(91)90043-l","type":"string"},"datatype":"url"},"type":"statement","id":"Q1177041$992E29CD-CA61-4F40-86A4-9F65239920A3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"597c0b15e2490b2c4529b787d75c948581ef25cb","datavalue":{"value":"W2071204190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1177041$D25B0593-5F81-4B6E-AE89-8E265080CBBC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7cdef7b785745d544e7a903a143eaa101e1bcd61","datavalue":{"value":{"entity-type":"item","numeric-id":3800030,"id":"Q3800030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"229aa7452c83e84746d45a42280e8e7e3554445e","datavalue":{"value":{"amount":"+0.9573122","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$70BE902C-9D24-4F59-86B0-CD8CA9B40279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4236c1d0af8d7c0f7abc80f4eba37327b39d445f","datavalue":{"value":{"entity-type":"item","numeric-id":5687325,"id":"Q5687325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f2a7ca69de0ec435abde2d3c690f618f24485ee","datavalue":{"value":{"amount":"+0.9296476","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$B007C1A6-1846-4D9C-A2C6-61DBF61DCFEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8eb64947ffb01544a4cc5eb29fd5da594dcb3f0c","datavalue":{"value":{"entity-type":"item","numeric-id":4207895,"id":"Q4207895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2bdf9220d9736c5c0a0a9ee1183fd209f2f3517","datavalue":{"value":{"amount":"+0.9091495","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$9A9E97B6-BCDF-46A0-94E3-FE651EBF091D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1df2f7774d4d4a498fc136dba94f052ced0bbe1","datavalue":{"value":{"entity-type":"item","numeric-id":1899144,"id":"Q1899144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db9241ff2113c60e693eca03dd4b614ab3a3814d","datavalue":{"value":{"amount":"+0.9021416","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$38A1F24F-73ED-4D16-B08C-EDD51C40AE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05dd3c0e3aea80a27cce19bded5bdca6fe00c822","datavalue":{"value":{"entity-type":"item","numeric-id":3606485,"id":"Q3606485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ef096cd788b2ec544a3b20d14480a46fc90dca7","datavalue":{"value":{"amount":"+0.89780235","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$B251A95C-8B0B-4B7E-A0D6-35752E33F0EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1383d6587f1d644c4b58d97e20f66c370f37d7fe","datavalue":{"value":{"entity-type":"item","numeric-id":3360848,"id":"Q3360848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6483d10b7454cb2c5fb56a71ea690904cb7b559","datavalue":{"value":{"amount":"+0.89731646","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$D5CDCD78-F745-4F47-87F2-3C05EA3CDFBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c4391ef12e51c3ce2230d0e5e03d87c41a53878","datavalue":{"value":{"entity-type":"item","numeric-id":3794177,"id":"Q3794177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccb24cc0c248110d88a2833ce410f52056af2ed6","datavalue":{"value":{"amount":"+0.8956884","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$C659B1FA-3243-4CF6-8506-AF16E2F6358D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9adb1bc7f1b88ff61fed7df161c4a5b1e92e6238","datavalue":{"value":{"entity-type":"item","numeric-id":1188294,"id":"Q1188294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2ad6f87acf775ce4a7a1483d84234533d099027","datavalue":{"value":{"amount":"+0.8929494","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$92776210-42C6-45D3-8AA5-7F8A97FFED1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"616ab76eab966f6c6a6441da808485224a21b7cb","datavalue":{"value":{"entity-type":"item","numeric-id":3520239,"id":"Q3520239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbae8a773861fad4f6c377978d2849da22df107f","datavalue":{"value":{"amount":"+0.8925913","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$B480A5A7-01F8-4D24-BD54-C4344C341121","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c85634a152828f5b387af46f85759fd1c0fc7b16","datavalue":{"value":{"entity-type":"item","numeric-id":4348126,"id":"Q4348126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6897d02793d2a1bff1c36ee17cb8c8fd19ff0d4","datavalue":{"value":{"amount":"+0.88987416","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1177041$27777EE1-434C-4644-B09E-66628A82CA4F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Bounded arithmetic and the polynomial hierarchy","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Bounded_arithmetic_and_the_polynomial_hierarchy"}}}}}