{"entities":{"Q1107524":{"pageid":1118273,"ns":120,"title":"Item:Q1107524","lastrevid":42882396,"modified":"2025-07-15T16:48:33Z","type":"item","id":"Q1107524","labels":{"en":{"language":"en","value":"More complicated questions about maxima and minima, and some closures of NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4064975"}},"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":"Q1107524$604A4352-1C43-44B7-A70C-B83B1D629D7D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"baef05248f6181ffc01e04fc8e4ce18ce98290bb","datavalue":{"value":{"text":"More complicated questions about maxima and minima, and some closures of NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1107524$46C8239D-4748-4982-8EEA-80FC915A6569","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09bd02602156e74408bc503fc9887c60810a5ab4","datavalue":{"value":"0653.03027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107524$6EBD12FC-76EF-47CD-83B5-FCF8DB2578A8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7fee117de68982d0d2f8b90b5007b2df4c1a5bb8","datavalue":{"value":"10.1016/0304-3975(87)90049-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107524$FDF1E4A9-6A02-48EC-9C19-F093EF63D0B2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05ccf9363a2b93804ef06018f3f40241df688bac","datavalue":{"value":{"entity-type":"item","numeric-id":675063,"id":"Q675063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$51312421-400C-49E0-A64B-3EF5D08C7A32","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$40DABC7F-3248-4A41-B24F-3E7EB8008E33","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1107524$E4D462C1-FA25-45BF-A137-0ECC67E81D46","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"749e4d4ab73968cb3f66d2034679cf01c2c2d069","datavalue":{"value":"Starting from NP-complete problems defined by questions of the kind `max...\\(\\geq m?'\\) and `min...\\(\\leq m?'\\) we consider problems defined by more complicated questions about these maxima and minima, as for example `max...\\(=m?'\\), `min...\\(\\in M?'\\) and `is max...odd?'. This continues a work started by \\textit{C. H. Papadimitriou} and \\textit{M. Yannakakis} [J. Comput. Syst. Sci. 28, 244-259 (1984; Zbl 0571.68028)]. It is shown that these and other problems are complete in certain subclasses of the Boolean closure of NP and other classes in the interesting area below the class \\(\\Delta^ p_ 2\\) of the polynomial-time hierarchy. Special methods are developed to prove such completeness results. For this it is necessary to establish some properties of the classes in question which might be interesting in their own right.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107524$2F608AC7-6DBA-47AE-98EE-AB10537351BF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107524$A497115B-355F-49D3-A372-D934EE48A66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107524$E3399966-2CB6-4342-886F-51563BAE071F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"415c163004444e7a3a05fca2d3415fc423f6e824","datavalue":{"value":"4064975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107524$B008F0C4-4B89-4601-B2FC-97D25525CAD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c8c9e80036612c21ad2ec3b6579e3228fd2ea1e","datavalue":{"value":"NP-complete problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107524$D0355BC4-0167-4C06-A210-BA004264862D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fce2cb886e13a48c130fcc8177587208674734bc","datavalue":{"value":"Boolean closure of NP","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107524$A09848DF-7BF7-4C5C-AF8D-D828DDB744F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"319f7aef6d48907b019428ced327b73484cf6132","datavalue":{"value":"polynomial-time hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1107524$CB2A3A94-E910-43CF-BAA6-2AECE56FBF34","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":"Q1107524$EE1AB592-6A38-4F01-B7C7-DFF3259970F0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4cce460da49b19e973093fe9d4aff30dca683054","datavalue":{"value":"https://doi.org/10.1016/0304-3975(87)90049-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1107524$72DBC4ED-0FCA-437D-B476-73D2C2F5F8E7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"00a53f59f936f998a1c2177d67e222e39d935e32","datavalue":{"value":"W2088044688","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1107524$21AA1121-9A46-4367-9891-482EA0AEE3CD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d5257f71d98a6e1899a8d1ff1a09a30fa28cbba","datavalue":{"value":{"entity-type":"item","numeric-id":3751004,"id":"Q3751004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$C83F8671-D1E8-45E0-9289-57FC0676065A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb5635d1f15d8e53fac7ea1c5fb3088cd96f14aa","datavalue":{"value":{"entity-type":"item","numeric-id":3029023,"id":"Q3029023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$8F8EA853-75BF-468B-8A58-9418A29B7E7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$54165028-5B03-4553-ABC5-0EADBB05EF76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$186AA2BD-BEA0-4415-8C8A-E36F7F236485","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7dc8eb86e4497e34b3d29c2f7331b0eb69507086","datavalue":{"value":{"entity-type":"item","numeric-id":5903066,"id":"Q5903066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$52956B8A-1E2F-4D42-A078-5E6BF4F02A32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a14259755a9136b7b26201f5111f10df5b52f768","datavalue":{"value":{"entity-type":"item","numeric-id":4109299,"id":"Q4109299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$D75193AB-7997-425D-B61C-2259637AAE39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7d15acf9b2dc594da15dc289088a8a93d59b4f8","datavalue":{"value":{"entity-type":"item","numeric-id":1223166,"id":"Q1223166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$41BF4384-B09E-4E54-866E-2D60902DCB28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"917800fa52c098f2382f946c4094dc39e957bfbe","datavalue":{"value":{"entity-type":"item","numeric-id":4153600,"id":"Q4153600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$44EAAFC8-2E0B-4773-9CEB-CAB8F2CEEA07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32c9cf122d104d7332be7d6610d7ce2681b03b64","datavalue":{"value":{"entity-type":"item","numeric-id":3768398,"id":"Q3768398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$A0C2D3D7-6271-42D0-8FBB-6D81D640FEDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800321fe9f6efe205a2eb283e0da5841a2b5eaad","datavalue":{"value":{"entity-type":"item","numeric-id":1061485,"id":"Q1061485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$97970E12-2171-483F-882A-B9815BFD8AE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f33f843778dfabfeef453cdfa627d4b42c24908","datavalue":{"value":{"entity-type":"item","numeric-id":4131648,"id":"Q4131648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$B8D0F9FE-B9F4-4233-B1E6-1A255A56BD7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$496A716C-0046-4B87-9CC5-FD45F933F75C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"656a88094d3818a28a699dfaea22a6fc84ea05fc","datavalue":{"value":{"entity-type":"item","numeric-id":3707407,"id":"Q3707407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$784A51BD-3BF0-48BA-81A0-F0D8FCC8F1AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd1e092eb099a32d4d756ee9e4c56322cfbee0af","datavalue":{"value":{"entity-type":"item","numeric-id":3873568,"id":"Q3873568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$3960EBE1-2EB0-49E2-B1A8-FD4376DFDBC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0e1c59b20b978e8e0de5a32fdeb6c212dbd6e1a","datavalue":{"value":{"entity-type":"item","numeric-id":1090455,"id":"Q1090455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$5EA16019-B7A1-43A7-972F-D806A8965228","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6af03520c6f6c29956d0277a652d1acf48dae7a","datavalue":{"value":{"entity-type":"item","numeric-id":3340147,"id":"Q3340147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$84C25280-65FB-4440-A823-B4C7121BEF73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f83662ae316121ea72100b37e1d7f310700b0f0a","datavalue":{"value":{"entity-type":"item","numeric-id":3703297,"id":"Q3703297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1107524$962FC1D7-9B46-4EF5-B6E1-C79FFDD95813","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6081dea17e6c176bd5281119892e40714f14622","datavalue":{"value":{"entity-type":"item","numeric-id":3766851,"id":"Q3766851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ed0d4a8002d98ae475e924c65685a1d36c2409a","datavalue":{"value":{"amount":"+1.0000001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$91923CB8-1D70-4F6A-9404-1E5355726335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f30ecffe16a5dfa4fff8644bcf1583e5970bcbca","datavalue":{"value":{"entity-type":"item","numeric-id":4029615,"id":"Q4029615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"531f73684809211e26ccade3452bc78c10b34f01","datavalue":{"value":{"amount":"+0.86562717","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$6B758182-FC6F-4A81-A277-EFB7B22CE2A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3864b37a7c5846b5a73ae46b9ee4b8920cfd3f69","datavalue":{"value":{"entity-type":"item","numeric-id":1827394,"id":"Q1827394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"590bf4642b588a6a0a32ce4f46137a9c0ca368a6","datavalue":{"value":{"amount":"+0.8323072","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$BA0CFE96-95CD-4CA8-AE46-176CB4B2E7A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3dd92df8908124f72dca3e8b46bd20b65c53139","datavalue":{"value":{"entity-type":"item","numeric-id":1960655,"id":"Q1960655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c21d3b190c9b4a9d6ae5c34c2f534dd56853b03","datavalue":{"value":{"amount":"+0.8221057","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$9A2DDEDA-32FF-41B3-8958-F655426D1FFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb25fda4a3498c2b9bb5c4c5c0bfa74daef3fd99","datavalue":{"value":{"entity-type":"item","numeric-id":3499721,"id":"Q3499721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8f2ee696af156a3a5c356a29fc882f081a751d0","datavalue":{"value":{"amount":"+0.81865126","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$CD015E25-C352-4B1F-91FA-4CA7B89FB6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81963fd22aebbec5c111d7a485d7807aa978ef7b","datavalue":{"value":{"entity-type":"item","numeric-id":2470035,"id":"Q2470035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8f2ee696af156a3a5c356a29fc882f081a751d0","datavalue":{"value":{"amount":"+0.81865126","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$AD62AF2E-6AE6-466A-B49E-99B3DA4EAABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f951a1e389f5f001491309a6e3d0a25b8b8c36db","datavalue":{"value":{"entity-type":"item","numeric-id":3783559,"id":"Q3783559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1350a447bb2bf5cb35aba125e23855b14c2bcdfb","datavalue":{"value":{"amount":"+0.8139023","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$EB2AE879-833D-4BF7-98A4-EE2357E1A269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf7a7b7416a19050cbb3a9816974f191820cf19c","datavalue":{"value":{"entity-type":"item","numeric-id":3167394,"id":"Q3167394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae6f5403cc124151996c2d4a8dcdccd367916d5d","datavalue":{"value":{"amount":"+0.8136552","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$14967F69-16CF-4785-9D37-C4EA30900B37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea07b18ea418f21242c276c1f19240ae3bbab464","datavalue":{"value":{"entity-type":"item","numeric-id":5419035,"id":"Q5419035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae6f5403cc124151996c2d4a8dcdccd367916d5d","datavalue":{"value":{"amount":"+0.8136552","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1107524$26A7931E-B5D2-4024-B398-B03F98B29126","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1107524","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1107524"}}}}}