{"entities":{"Q866565":{"pageid":868413,"ns":120,"title":"Item:Q866565","lastrevid":50030701,"modified":"2026-01-12T17:46:38Z","type":"item","id":"Q866565","labels":{"en":{"language":"en","value":"Derivability in certain subsystems of the logic of proofs is \\(\\Pi_2^p\\)-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5126406"}},"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":"Q866565$4B8CC8E7-5F52-4935-8BE6-CA9FD40B8046","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"da9255dcc1c1888ae55d0420ff5597df721eb25d","datavalue":{"value":{"text":"Derivability in certain subsystems of the logic of proofs is \\(\\Pi_2^p\\)-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q866565$3469E979-6F1F-4236-A43B-554E83EC3C53","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4f379b16b2ddca908ba48a3cc4aefb437cc40577","datavalue":{"value":"1112.03054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866565$41B74B22-1078-403A-80D9-A0A02D7F857B","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":"Q866565$D88D6F00-FC37-479E-BEAD-69BC8E7A8735","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a94159f4ab38d8d1a06ee095402a858d13e226d9","datavalue":{"value":{"time":"+2007-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q866565$05906514-7A43-42A8-90FF-A6C354D979F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"40a29e8d518e22f75a3ba6b382b373c2e3a3d24d","datavalue":{"value":"The Logic of Proofs LP, proposed by S. Artemov, is a realization of the modal logic S4 in which the modality is replaced with explicit terms representing proofs. V. Brezhnev extended the idea of explication to several subsystems, among which the K4 version is of particular interest as the Logic of Beliefs, and R. Kuznets presented a \\(\\Pi_2^p\\) algorithm for deducibility in these logics.  In this paper, the author shows that deciding derivability in several significant sybsystems of LP is \\(\\Pi_2^p\\)-hard by encoding QBF-2 as a formula of LP which can be derived only if the quantified Boolean formula is true. From this, in conjuction with the observations by Kuznets, it follows that derivaibility in each of the subsystems is \\(\\Pi_2^p\\)-complete, while the analogous problem for corresponding modal logics is known to be PSPACE-comple.","type":"string"},"datatype":"string"},"type":"statement","id":"Q866565$BCAF56FB-9ED9-4DF0-A0D3-002C2618FE54","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e3f06c5cc154fad665bbd7bfe01f3fd2207302a9","datavalue":{"value":{"entity-type":"item","numeric-id":588143,"id":"Q588143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$D4911561-F16C-4091-835C-54F569AD243B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b638c7935436ccffba7a737e2b57436cbbd2533c","datavalue":{"value":"03F45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866565$09030998-9B48-486D-9268-7911A3DB0FB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74a6cec96241e450625296e63e8dd539239d7104","datavalue":{"value":"03B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866565$B77AA8F7-221C-4669-B5B4-CDA0CADFB08F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866565$844A1F6F-5709-484C-8E37-38FF58D36DBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866565$179E58C8-0AB4-40D1-B1D1-9735D80C2FA9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6787e5e972cf49212f6e0a18e5582729a8993376","datavalue":{"value":"5126406","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866565$E7E42692-D168-4E6B-9821-F223EDA35A1A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e2e21a984526b8024b04acd04fd80cbaaf58f4b","datavalue":{"value":"logic of proofs","type":"string"},"datatype":"string"},"type":"statement","id":"Q866565$EA725C4B-24A3-43C8-B553-7C1A6B84E295","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9e3897b6c80275d8a1fea3f0a7c343ff302ba05","datavalue":{"value":"logic of belief","type":"string"},"datatype":"string"},"type":"statement","id":"Q866565$F5FF5BFA-A2BC-4E0C-B4D3-CB0A8BF0FCF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q866565$E12009B8-B281-4F95-A7AE-2EC647468261","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8450522eaf34ce6110696ce25ccf0bdbf4cb155b","datavalue":{"value":{"entity-type":"item","numeric-id":1776196,"id":"Q1776196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$32D8C538-4C7C-4C8F-ABF7-16E550B61DD4","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":"Q866565$9BD3E251-5954-4B08-901C-B986E80D0F55","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4c91611819aca2053f25f2b867168c1324c6d5b7","datavalue":{"value":"https://doi.org/10.1016/j.apal.2006.03.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q866565$D6902E0B-9278-4057-9280-6896B9146BBC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"28077d0b9851107d1b9d0b6ed73a68a092088b9b","datavalue":{"value":"W2138312950","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866565$0472ECA9-6FD3-4E72-AF8F-3B3870D2D01A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2c9a82b9ab82a960255476489c4b9e9354b122e","datavalue":{"value":{"entity-type":"item","numeric-id":4283226,"id":"Q4283226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$39441576-7B3D-4558-A35E-E0C87E0658EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e1a6ebb360b6bfc3a111b832b5231ca5c9153b7","datavalue":{"value":{"entity-type":"item","numeric-id":2732527,"id":"Q2732527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$A55292A2-13CA-420D-AFC5-923378DDFE8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f182e8d068c4ffda3ffda36b3ed008e8979c149a","datavalue":{"value":{"entity-type":"item","numeric-id":5692429,"id":"Q5692429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$3570D66B-A08E-498A-B85A-CF883B87A563","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e48db1b157c394a0b9d11039c5ebf7925b1a5648","datavalue":{"value":{"entity-type":"item","numeric-id":5292623,"id":"Q5292623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$48D3568F-C069-4238-9779-BFEF5C7D132A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1dc9f77118731d07defbe2b73ecd4ccb123bd5e","datavalue":{"value":{"entity-type":"item","numeric-id":703832,"id":"Q703832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$F23B98DF-4A66-42E3-9A87-8F50385C206F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b19af37d190007ff6ebc0d93b6c1957931f3dcf9","datavalue":{"value":{"entity-type":"item","numeric-id":4698331,"id":"Q4698331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$6D5315ED-AF4C-4227-8A9C-DBBA50F2FA24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62fe320a8e2945a982156f6d4f3d5b1f2e3ba92e","datavalue":{"value":{"entity-type":"item","numeric-id":2753686,"id":"Q2753686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$C8A5B1E4-B65D-4945-A166-5324A08D26BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21f66774e18bf6d9e857072576d53e1307dde765","datavalue":{"value":{"entity-type":"item","numeric-id":4149442,"id":"Q4149442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$B44D4AAE-3B5E-4A52-BC7A-63D840B56DF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dfbfd3fd8285c1b250d4a94e1be2061d1444016","datavalue":{"value":{"entity-type":"item","numeric-id":4376067,"id":"Q4376067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$0D8A6645-B920-40CD-8BF2-DB8C4C47EB4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$49B9E1C3-9EB5-42D4-B13A-E7752F7D65D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e499c86ee0646fff12cf3f079c9131faaea7b20","datavalue":{"value":{"entity-type":"item","numeric-id":4215637,"id":"Q4215637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$A780E35B-A416-40D8-A1DC-00E51BC4772C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"556c63d3d5fbb69adda2aaeb321f31370f38a3b9","datavalue":{"value":{"entity-type":"item","numeric-id":4716271,"id":"Q4716271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q866565$E54A4D55-BA47-4BDF-A23C-E8787D8D2A7F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bc59f92c5d1e77c3ccdd43f0c5a1e61f79647e2f","datavalue":{"value":"10.1016/J.APAL.2006.03.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q866565$3A805EF4-C824-4B2E-81B8-E74038374A38","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c0d0fa343c0b96a269f5396808d56db680ae857","datavalue":{"value":{"entity-type":"item","numeric-id":4829857,"id":"Q4829857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05cd8b0c988246eb7062429ef60800504f95dad3","datavalue":{"value":{"amount":"+0.8234652280807495","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":"Q866565$A1823B20-BE83-4A80-8812-B8B2253A8382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5dccaccc521147cc7b8d8115bf724de734a15384","datavalue":{"value":{"entity-type":"item","numeric-id":2500485,"id":"Q2500485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cf51e6e0f8f9f3955656dda0c32e314ebbf5352","datavalue":{"value":{"amount":"+0.8143419623374939","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":"Q866565$0A83D790-1E64-4924-B74C-F759A0C2B0DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"baf6280f84fd808018b787d293b83c19196a461b","datavalue":{"value":{"entity-type":"item","numeric-id":2753686,"id":"Q2753686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"419aa51c0bca52d7f0b7b5fbfc980fe93bfc1d4e","datavalue":{"value":{"amount":"+0.8030664920806885","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":"Q866565$368FAB85-085F-408C-940A-9A2BD594A5D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c513fccf75d24ea91bb857470b0ec8618fd1f7ed","datavalue":{"value":{"entity-type":"item","numeric-id":2500480,"id":"Q2500480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c263e9f5312d7b78af0e06f1131b892f7d500674","datavalue":{"value":{"amount":"+0.7983376383781433","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":"Q866565$83712457-1008-4602-9B56-B73A248612D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bade1c4d4b8c83dc9273b03a9c5e330219392210","datavalue":{"value":{"entity-type":"item","numeric-id":5957921,"id":"Q5957921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30b1a2d3682fc3e6ba8fcb5e26a2661d768f73a8","datavalue":{"value":{"amount":"+0.7970805764198303","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":"Q866565$65C2BE57-3CCB-4524-A5F2-4ADD115E6FF1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:866565","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:866565"}}}}}