{"entities":{"Q3715098":{"pageid":5745004,"ns":120,"title":"Item:Q3715098","lastrevid":110529185,"modified":"2026-11-17T14:26:41Z","type":"item","id":"Q3715098","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3943795"}},"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":"Q3715098$2A86D3D2-12EB-48CF-AC23-668329739776","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f8c5cc6d5adf22330abe6f7877a2b2d34d08612f","datavalue":{"value":"0588.03024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3715098$49CC9412-D907-4BC4-9392-E8C1FC3AE572","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f10e74d2799a0f84c55f8d253157b843029c56b","datavalue":{"value":{"entity-type":"item","numeric-id":926176,"id":"Q926176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3715098$8BB1789F-4353-4BCE-8809-A9BC930A754C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a4af4007b5ee47f98e190c53214defc298e1662e","datavalue":{"value":{"entity-type":"item","numeric-id":442257,"id":"Q442257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3715098$BDF55B1A-1F9F-4304-8542-9553638F9AEA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3715098$8E65E6E4-38EE-407B-9E32-17F11107CC56","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3715098$62E9DCC2-D5CE-46E7-90B8-16EC5A4872EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"33d9ad5fa3901c3c85d59a42af89ee043a9f83fb","datavalue":{"value":"03D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3715098$01FDC9F5-9061-4F5D-B1B2-EDC3458DD241","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"23ec81ba0f2474b4adbf1f28e835a9a12fd20d19","datavalue":{"value":"3943795","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3715098$C58C3881-5D3E-44EB-AB1F-94755DA300F7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"834c45d526445b63ede129bf0252d3b47bed13e5","datavalue":{"value":"NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$A669B43E-F2C2-4EB2-899C-235878C91A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3dfdaca4356dd055320bfd3fb7aa2393eb479dbb","datavalue":{"value":"polynomially bounded quantifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$92C2B4A1-199D-4CC1-A7C5-0CF43573F300","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c855ebe5d75fb44d339093306710aad93c187b9","datavalue":{"value":"probabilistic quantifiers","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$700E2866-6A83-4466-8B16-E413F9653FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d95edd6b76b4bdb73d152904f7825e8f74ba3b4","datavalue":{"value":"BPP","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$BDF0E040-1460-4441-B37E-DE6735B5EB42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8668dc3a1e2d6254dbefdd4a1f8224da396baed0","datavalue":{"value":"bounded error probabilistic polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$6359F913-C42A-4BB3-8D9F-B22B218856A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$3099214D-4B8E-4178-84ED-B016E240802B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c436e5aa792b026420149ecad404c3db266f2350","datavalue":{"value":"quantifier- classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$1B27E7DB-0CB4-4F61-B9CE-8378879A7C7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"623d0a2a145290cc1b1264c0c599570456aa3448","datavalue":{"value":"polynomial-time complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$DBB5CBB4-BBA8-4B66-8458-406FE98A3A14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96c107bb63de79565718d188b33fcc483957cfdd","datavalue":{"value":"PSPACE","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$542694A0-8AE0-4A59-9A62-F89DA6B3307D","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":"Q3715098$D5BFF8FE-50AC-4D45-9806-46E21354B859","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b67c511b8f60297e1d065c471e8f091898726552","datavalue":{"value":{"entity-type":"item","numeric-id":1112019,"id":"Q1112019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6143e04cd6eb8b6efd327b6848b9c813cded93b","datavalue":{"value":{"amount":"+0.8432238101959229","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":"Q3715098$9FFD1A49-76B8-4BD7-859B-A29805DAC774","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dda3856c7368c14820f1391ef1305710f4a7e3b8","datavalue":{"value":{"entity-type":"item","numeric-id":4725751,"id":"Q4725751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3239f78e3a540d34a726d770c4e2cd82eec4bfc","datavalue":{"value":{"amount":"+0.8285298943519592","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":"Q3715098$E2459B5E-235A-4079-B0DA-F913E4D55408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97f7667550558b98dc3cb8ffc54a893a7c13b8a4","datavalue":{"value":{"entity-type":"item","numeric-id":1186606,"id":"Q1186606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa85493d4fd82010b7436bbb8e470c0bf57d82a6","datavalue":{"value":{"amount":"+0.8254432678222656","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":"Q3715098$A2047240-6FCC-4281-A0B4-620C5FC7BF14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d9031b73ffb0f4c256e887d2438ff51cf9e7d9d","datavalue":{"value":{"entity-type":"item","numeric-id":3761699,"id":"Q3761699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa85493d4fd82010b7436bbb8e470c0bf57d82a6","datavalue":{"value":{"amount":"+0.8254432678222656","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":"Q3715098$F02A5AE6-EFC9-4329-B497-01108DB4E614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"534eeb09337670d9acf4de6b0c0c9942a78d778b","datavalue":{"value":{"entity-type":"item","numeric-id":3345785,"id":"Q3345785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81970fd9a096aef29f0cc3a4cc3eecc76ea181c5","datavalue":{"value":{"amount":"+0.8207062482833862","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":"Q3715098$58183F06-96BD-4377-8C64-18D8909729A0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6756b3c2ea9a67a52de2e98edb16b5c242fae9f8","datavalue":{"value":"10.1007/BFB0076220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3715098$97EE90CA-65CB-41AA-BCA0-8AF72BE1355F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"03c442e021d5e1dae353bcf6205ac9768ea7a6d3","datavalue":{"value":"[For the entire collection see Zbl 0566.00001.] It is well-known that a language \\(L\\subseteq \\{0,1\\}^*\\) belongs to the class NP if and only if there exists a relation Q belonging to the class P such that \\(x\\in L\\Leftrightarrow \\exists y (Q(x,y))\\) or, equivalently, \\(x\\not\\in L\\Leftrightarrow \\forall y \\neg (Q(x,y))\\), where y ranges over strings of length bounded by a polynomial in \\(| x|\\). In such a case the authors say that NP is characterized by the quantifier pair (\\(\\exists /\\forall)\\). Changing the above mentioned meaning of \\(\\exists\\) by ''there exist many'' or by another meaning, one can define a series of ''probabilistic'' complexity classes in terms of pairs of strings of polynomially bounded quantifiers applied to relations in P. Theorem 2.5 gives a characterization of known complexity classes in terms of probabilistic quantifiers. The authors obtain a series of general results concerning strings of probabilistic quantifiers. The class BPP (bounded error probabilistic polynomial time) is investigated thoroughly. Complexity classes defined by use of Turing machines provided with oracles and relationships between the oracle-machine classes and quantifier-classes are investigated. For any complexity classes C and D, the authors define ''\\(\\to ''\\) as follows: \\(C\\to D\\) if and only if for all oracles X, \\(C^ X\\subseteq D^ X\\). \\(C\\Rightarrow D\\) if and only if \\(C\\to D\\) but \\(D\\nrightarrow C\\). Investigating relativizability of inclusions \\(A\\subseteq B\\) among complexity classes, the authors survey and prove several new results concerning \\(\\to\\) and \\(\\Rightarrow\\)- relations among 18 fundamental polynomial-time complexity classes lying between P and PSPACE.","type":"string"},"datatype":"string"},"type":"statement","id":"Q3715098$45394076-6BCD-4C2B-8161-E50E2743C68D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"583d5634d5ee6575aaa37bb42a0c5602371241ea","datavalue":{"value":{"entity-type":"item","numeric-id":163387,"id":"Q163387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3715098$403EF0E4-9C66-410A-B609-3A4CA5DD86C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3715098","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3715098"}}}}}