{"entities":{"Q5092409":{"pageid":7121985,"ns":120,"title":"Item:Q5092409","lastrevid":55417216,"modified":"2026-02-17T15:58:50Z","type":"item","id":"Q5092409","labels":{"en":{"language":"en","value":"P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7561691"}},"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":"Q5092409$43403FE3-C2AA-4AB9-954E-64475C4C6D7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"366c77768321fada60910ad753881af032dcd901","datavalue":{"value":{"entity-type":"item","numeric-id":2182322,"id":"Q2182322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$665CD0DD-BBDC-4A69-B194-188F15B9AC83","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ae3e014d42c3e727189349ca8167d2ae32144d1","datavalue":{"value":{"time":"+2022-07-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":"Q5092409$ACD05EF2-9462-452C-8178-D4D70F4182CD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f969879f531643f058f8dd4c87a7dd4eb7b8c4c8","datavalue":{"value":"68Qxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5092409$1CF5362A-907A-4D28-8F1F-BAF6FC058986","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"666fe6041705e046f5d01e912ca5e57e79450c60","datavalue":{"value":"7561691","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5092409$AA1A5225-9549-46D0-B937-3B42C9747FD3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q5092409$BF232664-8EA0-4B9E-BFAF-0FDBC7043561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc028f491ca3cd6c7521dd6f6f17a35cdad54a6d","datavalue":{"value":"proof systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q5092409$4CDF2985-2395-4402-A6DE-51609D22CA1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd868c11b3e625fa1920a4ad16e472ee413a66e9","datavalue":{"value":"disjoint NP-pair","type":"string"},"datatype":"string"},"type":"statement","id":"Q5092409$88AECA13-6B7B-4315-9507-76AAF83DDBB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac873341ab34d6db98676ef037e18583cae25841","datavalue":{"value":"oracle","type":"string"},"datatype":"string"},"type":"statement","id":"Q5092409$43501F46-F931-4A73-9E92-88FA0884E586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8857014f30b7ec4403f873adf31e4da602963762","datavalue":{"value":"up","type":"string"},"datatype":"string"},"type":"statement","id":"Q5092409$CB1ED0D5-14EE-485D-B4BD-DFCF6D28A1D4","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":"Q5092409$39866DD4-2504-4B66-8CE6-F66A37FFA984","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7592b023ac89204897ab3bc752fbf29f253474a","datavalue":{"value":{"entity-type":"item","numeric-id":837177,"id":"Q837177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$DBE1EE49-F639-4168-92A6-F163B7AA3617","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bea75da9fa67a5f77faa9362cd4aa6c737c792a","datavalue":{"value":{"entity-type":"item","numeric-id":4194955,"id":"Q4194955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$FBA5690B-9AF2-40A1-A052-64993F4AD1C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9d6d960e351c80be000f302db6efef14ab7325b","datavalue":{"value":{"entity-type":"item","numeric-id":4651518,"id":"Q4651518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$BD882A0B-AEDF-46C8-A321-CA3015FE41D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1aa96b7c0ec9bc7a683e7636e258c3fded01e42","datavalue":{"value":{"entity-type":"item","numeric-id":3787917,"id":"Q3787917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$09C865C3-6B05-443E-BCD6-7726BFF914BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd07bc9a9b69ce8a80cf38ac60dbedf570ebf67d","datavalue":{"value":{"entity-type":"item","numeric-id":1109566,"id":"Q1109566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$18C197FE-D23F-4ABA-9396-A644BF717E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbb6ffdc2da3f7f9fdafbed4d441b6ee26762fc8","datavalue":{"value":{"entity-type":"item","numeric-id":4472459,"id":"Q4472459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$8AA215E9-887A-4AC4-AC59-B2DA3B8D51D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559db777cfd8d3556503f38e6f593a8dea97b362","datavalue":{"value":{"entity-type":"item","numeric-id":1398371,"id":"Q1398371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$92F42729-100E-45D9-AA57-A1BEA57227CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25f4a86512e0f02bf82877dbb62313fcd7fe9ed1","datavalue":{"value":{"entity-type":"item","numeric-id":3472096,"id":"Q3472096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$A683B6F0-E9D8-48F1-9B3E-A561483B016E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eecc3b6d7dd71b319d9179536e3a71e5676e3a6b","datavalue":{"value":{"entity-type":"item","numeric-id":2366687,"id":"Q2366687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$BD67FA90-2BF5-4F9F-8E61-52DC961AA8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$20A0DB49-6BC6-4996-8E52-6FD629CBAAC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"463d5da9ce3bd717aa94af12374b31584172a9f4","datavalue":{"value":{"entity-type":"item","numeric-id":4885911,"id":"Q4885911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$944ACB7F-F342-48DC-B0F4-F78C0EF7448C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f988a28c6c270b39799b8ecc681337eb8b872d4c","datavalue":{"value":{"entity-type":"item","numeric-id":4913583,"id":"Q4913583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$C4EEB5F2-80D7-43C9-A054-C9CDAB036023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62756db01e363051fb903b58c62718f57d2ec5c4","datavalue":{"value":{"entity-type":"item","numeric-id":4640304,"id":"Q4640304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5092409$05922DE9-F2E1-43C5-A982-2E86B8635524","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3c2549189fd53b2cd3c37a468ae1810ba1f55235","datavalue":{"value":"https://drops.dagstuhl.de/opus/volltexte/2019/10991/pdf/LIPIcs-MFCS-2019-47.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q5092409$2831411C-E260-4789-AB74-58226A0CA75B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"66ef66058553469585e7b3d90e5a0f8902e68cd6","datavalue":{"value":"W3213397036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5092409$25F976D2-09D0-43DC-AF5D-C854D9AB9083","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"56fd84caa005df7342cd1586a4781bb1fc72b7d6","datavalue":{"value":{"text":"P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5092409$C6CF70BF-8AA9-4ADA-8A93-F13C322C6948","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a82c899bb6572d22a0ee1255a61fcb2316bec09e","datavalue":{"value":"10.4230/LIPICS.MFCS.2019.47","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5092409$7EC951D5-3009-4A9F-B2D6-5B55E3AE8B23","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"368969fd906dbf7135dd97d6869ffae328837494","datavalue":{"value":{"entity-type":"item","numeric-id":2290649,"id":"Q2290649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3466c1ffbb2a782e66e6874e486e9e62d92cf3e4","datavalue":{"value":{"amount":"+0.9466038942337036","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":"Q5092409$61E2C79A-D798-49F9-A979-71140AB3F5C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ddc502250e162aa0f40c7468f3c2679f25f7a96b","datavalue":{"value":{"entity-type":"item","numeric-id":4651518,"id":"Q4651518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27b538b32b3cd996b3189d25c0b4792248633970","datavalue":{"value":{"amount":"+0.886831521987915","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":"Q5092409$C551386C-28E2-4F5A-B48D-C015773D3DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78c304c6a1a0792f2235e3da0511be7d19a30d47","datavalue":{"value":{"entity-type":"item","numeric-id":2210516,"id":"Q2210516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00735af33860a8cccd80e1996d0571807721cf5c","datavalue":{"value":{"amount":"+0.8830883502960205","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":"Q5092409$4F3C23F5-3F62-4422-A765-3884692FC035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a553968c20f72dc4a7c04371e13f048cae8585b3","datavalue":{"value":{"entity-type":"item","numeric-id":3436752,"id":"Q3436752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ea331f9c4b5eae96ee0f7b32c7b61092feb3847","datavalue":{"value":{"amount":"+0.808562159538269","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":"Q5092409$934FFB25-A27A-4B48-B4F1-4E63F8783B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80b229f27005b3ddd16863d120c83416fe77a57c","datavalue":{"value":{"entity-type":"item","numeric-id":5492875,"id":"Q5492875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d137fee6f7ba3b337e147e944e5935eb6a665ba","datavalue":{"value":{"amount":"+0.8035023808479309","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":"Q5092409$B46E56D4-5C41-4E48-AAD5-1567B7A3650D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5092409","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5092409"}}}}}