{"entities":{"Q1106665":{"pageid":1117414,"ns":120,"title":"Item:Q1106665","lastrevid":69656550,"modified":"2026-04-13T08:30:17Z","type":"item","id":"Q1106665","labels":{"en":{"language":"en","value":"Geometric optimization and \\(D^ P\\)-completeness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4062590"}},"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":"Q1106665$32667B5C-0A65-4A58-BA64-C20AA01CD6CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5cd7d52ad4b0ecb16c1d748f45768a7aa6eb8181","datavalue":{"value":{"text":"Geometric optimization and \\(D^ P\\)-completeness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106665$E1B31E3D-412B-4285-94B6-9726B695C8BA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6194d44c0c18034a6bc5f9219c493119525f29ef","datavalue":{"value":"0651.68055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106665$0E63D579-F368-466A-A914-5000B25DE0AD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a3e0e3cc4a15a4ad9cb1f4752c50e2b4e064b079","datavalue":{"value":"10.1007/BF02187711","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106665$B8F1106A-2379-41AE-B731-18BE8A626C6E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e666d41882411f9ee5a3d11cf0ad33cabba8b2","datavalue":{"value":{"entity-type":"item","numeric-id":672057,"id":"Q672057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$466CD967-7F6D-45C2-B8DE-1DF31D80054C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"325004719c38716601c5254a9dd4bc70016546ac","datavalue":{"value":{"entity-type":"item","numeric-id":917301,"id":"Q917301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$86B249D4-9559-415F-9581-E185B1C9EAB1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$2A3B600C-702B-47B4-BE5F-8F9EE2985513","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1106665$F6B4D988-D734-4804-BF03-F24369DEEF76","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b2a1aa95d3d7cbb67466f7073d7c5307e9a1e565","datavalue":{"value":"https://eudml.org/doc/131060","type":"string"},"datatype":"url"},"type":"statement","id":"Q1106665$8476F238-A268-4103-8E6F-C4D722320A14","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e2de6cf82c74a9c149d078098bedf8be536bf7cf","datavalue":{"value":"The task of classifying the complexity of optimization problems accurately in the polynomial hierarchy is one of continuing interest and importance. We show that a large number of geometric optimization problems, that arise naturally from the optimal placement of simple geometric objects are complete for a class \\(D^ P\\). The class of \\(D^ p\\) is defined as follows: L is in \\(D^ p\\) iff L is an intersection of \\(L_ 1\\) and \\(L_ 2\\) such that \\(L_ 1\\) is in NP and \\(L_ 2\\) is in Co- NP. The class \\(D^ p\\) contains both NP and Co-NP and is contained in \\(\\Delta_ 2^ P=P^{NP}\\). Completeness in \\(D^ p\\) is exhibited under many-one and positive reductions. These results also prove the existence of natural geometric optimization problems that are proper in \\(\\Delta^ P_ 2=P^{NP}\\). Further OptP(O(log n)) results are exhibited for some of these optimization problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106665$0ED595B1-5838-40E4-A64C-7AD69811B992","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106665$F3D6004E-CFAB-4092-A61F-9E251B70C4A4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"78ab9440766bc78d1d3fd98b9e9aad58d5d6e83a","datavalue":{"value":"4062590","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106665$A2969F29-6723-4C05-BE29-21CCC0AF248F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"edd452f07ff284953f3a8a7af6f49f724d3f8826","datavalue":{"value":"\\(D^ P\\)-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106665$65CE262F-79F5-4BCC-BABA-44E77065DE03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccda4465483a2fabee4b4dc7ab7c4127fd1fc762","datavalue":{"value":"complexity of optimization problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106665$B6AB38EC-5724-4D6C-8994-BDAD3E1954F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106665$9621BD3E-6CCB-4AE9-B028-0E077EB1F8C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a2849fed3479edb812a736a871bd6b69ff9f050","datavalue":{"value":"geometric optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106665$1CA73D56-051E-446E-86CF-A8ADECF66455","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":"Q1106665$4E890672-9C4D-4291-8E26-5C0F5D34FDBD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$694D245D-57B4-4264-9EDC-FAF8A821BFA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ba5c382c28e072c4c988db9c9dcc2fcb79e3473","datavalue":{"value":{"entity-type":"item","numeric-id":3083284,"id":"Q3083284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$E88B03D9-451C-4A66-91D0-F93CE184E2F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f10f3124af56047b3a7731cdb89fbe3bd75b1213","datavalue":{"value":{"entity-type":"item","numeric-id":1104865,"id":"Q1104865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$733EA81A-10CF-4C0F-91BD-B333D6E45501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ec04ea7ead28f8e6bc5f36d8da9c4a49fc33004","datavalue":{"value":{"entity-type":"item","numeric-id":5579680,"id":"Q5579680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$DE30A1C8-6E85-4BDA-B431-62BCDB75A9F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"307fb49f6fe2fb59c207608c4367a76916d437d2","datavalue":{"value":{"entity-type":"item","numeric-id":1157170,"id":"Q1157170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$0D41B906-2F7E-4E19-B9C7-02D13B9CBC4E","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":"Q1106665$69A4CE49-075E-449C-99E3-EA96E9A829BD","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":"Q1106665$A6A13A0A-2CB3-4039-AE55-4D8B78387A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd10c34718a207890d8316984bdb5966c1dd019f","datavalue":{"value":{"entity-type":"item","numeric-id":1152218,"id":"Q1152218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$8DAC77AA-1062-47BF-A1CA-C43EA140ADAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5c3ddd4007917f647a575807ea575e87e66138e","datavalue":{"value":{"entity-type":"item","numeric-id":3318110,"id":"Q3318110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$BA367A1D-F720-4605-9EB8-52A29B1D1776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd76cce0bffb6a69bf9543126ec554d14d378d0d","datavalue":{"value":{"entity-type":"item","numeric-id":3148759,"id":"Q3148759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$E122E52C-F09B-439C-837F-0D2E6F7DF7AC","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":"Q1106665$FCC7334C-50A6-44DE-A7B9-342195B3EF44","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":"Q1106665$78F83C6F-6EBF-41FF-8A3F-38F06BA3FAFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d18e4b439adfecff09b2cf1367d09302baaa3617","datavalue":{"value":{"entity-type":"item","numeric-id":4739905,"id":"Q4739905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106665$D2E2E9FA-94EC-426E-975F-FCD79BE05345","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"96873605ce84fc16c45d0f4c5168979452f2c573","datavalue":{"value":"W2210827803","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106665$E852124A-6E24-4E1F-9D61-6FF3D17208A4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"720c6a2ec3adc4218d2435e28ae9412137d913a4","datavalue":{"value":{"entity-type":"item","numeric-id":3732962,"id":"Q3732962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3efe3609ac968862b925c54cf1e4388328173b53","datavalue":{"value":{"amount":"+0.878070592880249","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":"Q1106665$0126077F-E597-4D77-AB57-FC939D7DA482","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a33bb1713eb71833beaacb0f8553c8951fc25d8c","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffe8002fc3bf58a9ce1917e8a0e7c1e0a5f0d8ab","datavalue":{"value":{"amount":"+0.7753218412399292","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":"Q1106665$19FE4559-4600-468A-8A54-A22A28692CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"faa7df9670c7b1e510b1908af4dd2f4f338b24e2","datavalue":{"value":{"entity-type":"item","numeric-id":1061485,"id":"Q1061485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0adebb9b9a699827288da7913c31ca01c962b5d1","datavalue":{"value":{"amount":"+0.7726722955703735","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":"Q1106665$303F510F-FF3A-4B3C-B5A4-E1833D1D68AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78dc40af4c2edbf4482704210b603e6ae4903b0f","datavalue":{"value":{"entity-type":"item","numeric-id":4289637,"id":"Q4289637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ed038fd0b1e4c1b0ce6cb2623307c5274b13497","datavalue":{"value":{"amount":"+0.7706990838050842","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":"Q1106665$2E167EFA-8D04-4F40-A50B-204BACFAD65F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4202e09d2912f97973b787cab5f0f1b205f85d1","datavalue":{"value":{"entity-type":"item","numeric-id":4780111,"id":"Q4780111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"41ba3ea4da67a078b3351a8b7508662317fa7c76","datavalue":{"value":{"amount":"+0.7703832387924194","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":"Q1106665$CFF79F57-8537-407B-95B7-E2C659C8798E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Geometric optimization and \\(D^ P\\)-completeness","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Geometric_optimization_and_%5C(D%5E_P%5C)-completeness"}}}}}