{"entities":{"Q2863169":{"pageid":2873889,"ns":120,"title":"Item:Q2863169","lastrevid":55919875,"modified":"2026-02-21T03:56:10Z","type":"item","id":"Q2863169","labels":{"en":{"language":"en","value":"Complexity for probability logic with quantifiers over propositions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6231636"}},"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":"Q2863169$47B691A8-D2DD-4ABC-ACD2-48CBCC90BF57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"195a82a57f18debe38b89b91c3e02d781cd85c82","datavalue":{"value":{"text":"Complexity for probability logic with quantifiers over propositions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2863169$34008CB2-FEE8-40FB-91DD-2E8EBF06DFF6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"96b835dd58670cb432e019cdb1562c02ebb8da9b","datavalue":{"value":"1309.03009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2863169$1C236BCC-A026-4195-B983-11EF775E0E9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f517762c8bf8d062c2939388e57760160d03abdd","datavalue":{"value":{"entity-type":"item","numeric-id":365660,"id":"Q365660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2863169$87D1FF48-CF34-4970-8802-F6CD9459E35F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cdd4a751ba4fdcf728e9ea46a31d246e59bdb21f","datavalue":{"value":{"time":"+2013-11-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2863169$544FFFF3-939D-4442-8CF2-2324DB66441C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"0e3678c4c27859448aaf57c0c464a06d6cc1a175","datavalue":{"value":"03B48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2863169$CBCDBF96-F9B1-4C60-B737-4CEDB754B764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2863169$80D521E9-E581-433E-A4AF-724EA6958A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2863169$75C38B4E-0980-4695-B025-B56177918ECC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f81f78bb00a7f207553bc2fb5fa16bcdad2f1d6c","datavalue":{"value":"6231636","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2863169$2AADF914-8612-41FD-9766-60AC5607B1BC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1514011e463f4b96b73949f9956db3dccc72fb4","datavalue":{"value":"probability logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2863169$8721F54A-9F48-427D-B371-1423D3AF258B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48fe5da30f2000a910dd1a06f280ea2b3174328d","datavalue":{"value":"decidability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2863169$839913A9-BA32-429F-B2A1-C44A30B8E7C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2863169$EBCA89B8-6113-4CB4-981B-3CBECD1C38BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78e469cb56ef748b3f9619abee5f10dfa052a7b9","datavalue":{"value":"expressiveness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2863169$FD476BFC-08C6-45EE-8BF8-F1A4AD5C015B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cceda8deea91fd98c336948592e2e8bfa2d9a133","datavalue":{"value":"quantification over propositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2863169$8C5AF413-E9BE-42D0-9E9A-A06C12C55220","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":"Q2863169$579F392F-E683-4FD9-BCEB-A76579B97D1D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"301d5f5eea0e4f3171e2e9216156b21942ee23bd","datavalue":{"value":"https://doi.org/10.1093/logcom/exs041","type":"string"},"datatype":"url"},"type":"statement","id":"Q2863169$6EAE35A4-F583-4FC4-8E28-A1FD43F8AB75","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"44c6c49ef80e14a7f2f0ce7b1018a5a13786c795","datavalue":{"value":"W2146907658","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2863169$1D2A145B-003E-46DB-A893-4724BEADE524","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0a1e265cb253c91cd72cb01c7224f14b448deb3e","datavalue":{"value":"10.1093/LOGCOM/EXS041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2863169$6B85838A-1A34-44B9-87E3-83019D0B13B1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4e284497c1d95ed03031b32369f55bf404c9e002","datavalue":{"value":{"entity-type":"item","numeric-id":6768690,"id":"Q6768690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2863169$5D13C137-1FE6-4D13-B086-7263F6C0A1CF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"48c8d8441dc9d7697f6af174f5e49324cf5ad1a0","datavalue":{"value":"This dense paper consists of four sections and an appendix. The first section contains a brief introduction to probability logic and complexity issues therein as well as a summary of some of the results which are derived at a later point in this paper.NEWLINENEWLINENEWLINEIn Section 2, the author introduces \\textit{quantified probability logic}, \\(\\mathcal{QPL}\\), by giving the syntax, the semantics and how it relates to other well-known languages. \\(\\mathcal{QPL}\\) is build up from the usual propositional formulae, polynomials with rational coefficients of \\(\\mathcal{QPL}\\)-terms and Boolean combinations of \\(t\\leq t'\\) where \\(t,t'\\) are \\(\\mathcal{QPL}\\)-terms. The author goes on to state that \\(\\mathcal{QPL}\\) is an extension of \\(\\mathcal L_{\\mathrm{FHM}-5}\\) and a very small fragment of Hoover-Keisler logic.NEWLINENEWLINENEWLINEWith quantifiers present in the language, the validity and satisfiability hierarchies \\(\\mathrm{Val}-\\Pi_i-\\mathcal{QPL}\\), \\(\\mathrm{Val}-\\Sigma_i-\\mathcal{QPL}\\), \\(\\mathrm{Sat}-\\Pi_i-\\mathcal{QPL}\\), and \\(\\mathrm{Sat}-\\Sigma_i-\\mathcal{QPL}\\) are defined in Section 3. The main result in this section is Theorem~3.6 which states that NEWLINE\\[NEWLINE \\Pi_0^0\\equiv_m \\mathrm{Val}-\\Sigma_1-\\mathcal{QPL} \\lneq_m \\mathrm{Val}-\\Sigma_2-\\mathcal{QPL}\\leq_m \\mathrm{Val}-\\Sigma_3-\\mathcal{QPL}\\leq_m\\ldots .NEWLINE\\]NEWLINE Section 4 contains a complex proof of NEWLINE\\[NEWLINE\\text{Theorem 4.1. The validity problem for }\\mathcal{QPL}\\text{ is }\\Pi_1^1\\text{-complete}.NEWLINE\\]NEWLINE In the appendix, Hilbert's tenth problem for rational coefficients \\(\\mathrm{DE}(\\mathbb Q)\\), rather than integer coefficients, is related to the material in this paper. The author shows that \\(\\mathrm{Sat}-\\Pi_0-\\mathcal{QPL}\\leq_m \\mathrm{DE}(\\mathbb Q)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2863169$A6EF23C7-7E85-4FA2-A4AD-69304899437A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c99d7bab7860e6ef95ce58f09e3829be39b50561","datavalue":{"value":{"entity-type":"item","numeric-id":280545,"id":"Q280545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2863169$101D2C21-B083-4D72-A5A1-748036C38F4C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0eadc692c954c3a8cc55b7925f441dc3ed0be20f","datavalue":{"value":{"entity-type":"item","numeric-id":384407,"id":"Q384407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5d259157615aadc044d19769c90b7f624677842","datavalue":{"value":{"amount":"+0.8165508508682251","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":"Q2863169$7672D305-2D92-464E-A278-111985EC08C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23ee07fb2ef41c05cea06a922fab5463e3a725ea","datavalue":{"value":{"entity-type":"item","numeric-id":695788,"id":"Q695788"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75fcdc23f5a25efc4882cd8d0266755f5772f387","datavalue":{"value":{"amount":"+0.8005630373954773","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":"Q2863169$A649B07D-DADA-441A-9797-B83C260D915A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b8dd5c37edcd7f51f6bbe4dcc16fce0e3731a3a","datavalue":{"value":{"entity-type":"item","numeric-id":3455849,"id":"Q3455849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b0a49c81d17f2f0a1d48113525285db69d7f5b7","datavalue":{"value":{"amount":"+0.782062292098999","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":"Q2863169$E800B647-6D74-442E-9298-7F2D0E6AEEC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f56de4e2e3e6194f18d6a339f9c19afe9aecdfb","datavalue":{"value":{"entity-type":"item","numeric-id":4593244,"id":"Q4593244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54fc8f2ff25ee17fb1db702c99d44e92b9783e88","datavalue":{"value":{"amount":"+0.7776883244514465","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":"Q2863169$F81661A8-6FF1-403A-8BAA-82C4249DDFDB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2863169","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2863169"}}}}}