{"entities":{"Q1119020":{"pageid":1129769,"ns":120,"title":"Item:Q1119020","lastrevid":66781095,"modified":"2026-04-12T12:49:19Z","type":"item","id":"Q1119020","labels":{"en":{"language":"en","value":"On the complexity of polyhedral separability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4096782"}},"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":"Q1119020$6245EAFA-6E5A-4172-B8F3-5F6A88F88128","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"737a884e9f7512b09e1193bb66e5951b08705c91","datavalue":{"value":{"text":"On the complexity of polyhedral separability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1119020$BDD0FB29-1E6D-4956-B0D8-D4D768533774","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f29219e755c1c7721ac6b35f94ee5c8ac863e44","datavalue":{"value":"0669.68035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119020$CB5CF14B-40EE-4C49-A5F1-DA7C3C96FD68","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9371f4b4c865da6112297ad7d54f3773e6e712b0","datavalue":{"value":"10.1007/BF02187916","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119020$31DB886B-379A-40D6-BE40-7276334534B5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be690050f94666bf6766a43de05350885a6401a1","datavalue":{"value":{"entity-type":"item","numeric-id":613423,"id":"Q613423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119020$17CB943D-1A79-44E9-89BC-15EADFF3AD67","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":"Q1119020$3B3BC348-399C-4779-8FE6-6472F72F1013","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1119020$2B028C78-A892-46CA-BD65-F10F0C32C808","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e2aff9f2840bfba41ce7cd4ff885fe824746499c","datavalue":{"value":"https://eudml.org/doc/131054","type":"string"},"datatype":"url"},"type":"statement","id":"Q1119020$32D143E5-2291-4966-AC86-5F8FC62E7453","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9c577d32745bbe639963f8120473649da67e96b4","datavalue":{"value":"Zwei endliche Punktmengen P,Q in \\({\\mathbb{R}}^ d\\) k\u00f6nnen durch k Hyperebenen getrennt werden, wenn es k Hyperebenen so gibt, da\u00df jedes Punktepaar \\(p\\in P\\), \\(q\\in Q\\) durch mindestens eine der k Hyperebenen getrennt wird.    Zu erkennen, ob zwei endliche Punktmengen in \\({\\mathbb{R}}^ d\\) durch 2 Hyperebenen getrennt werden k\u00f6nnen, ist NP-vollst\u00e4ndig. Zu erkennen, ob zwei endliche Punktmengen in \\({\\mathbb{R}}^ 2\\) durch k Geraden getrennt werden k\u00f6nnen, ist NP-vollst\u00e4ndig. F\u00fcr festes k und d braucht es polynomiale Zeit, um festzustellen, ob zwei endliche Punktmengen, in \\({\\mathbb{R}}^ d\\) durch k Hyperebenen getrennt werden k\u00f6nnen.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119020$34491385-4081-4B0C-95B1-9CCDDF120462","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119020$BCFB4AE4-05EF-4449-885F-91EEC9933823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa4669cf5eaa224b5d3554d9705827ca09f43afb","datavalue":{"value":"52A37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119020$47753882-5E7F-4E57-981E-A75E91346032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119020$A7618A29-D832-410E-8CAA-DCCA975E2FB8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e4d098beeb69a7d2831a78ffc4ce4f5f39d1f463","datavalue":{"value":"4096782","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1119020$3987F995-330F-4BD3-9A84-E298174696E2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119020$CF2F5CDC-F3A5-49FB-A0E0-691CE7D6244B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9db2bcc80bf32b479e44cc4cb097c9fd18f1c048","datavalue":{"value":"polyhedral separability","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119020$DA74BA71-FF1B-4D48-8DD3-27F97C382495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119020$5187FF45-3213-4978-89D2-4758A6B82830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bc7da3f620934bd0169fd703d0ce0e3c6ec3f79e","datavalue":{"value":"linear separability problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1119020$FD9AA501-8AEE-46F8-890E-E1608EBEFD40","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fc5fc43392f13948d996ebe372a4d176799cfbac","datavalue":{"value":{"entity-type":"item","numeric-id":998234,"id":"Q998234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119020$C79FA02B-AB85-45AF-BE8A-3D0364AA02C5","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":"Q1119020$28DEB4E3-8E4D-4F2C-B525-22E1F49AE0C4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"412700c266a85a75e9cea4667313dd36123a2fba","datavalue":{"value":{"entity-type":"item","numeric-id":1101685,"id":"Q1101685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119020$8C6879F2-5042-4CAA-BFFA-FA9D5BAF9FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a9e941b224ae72629b3e2cd083153eeebdfa379","datavalue":{"value":{"entity-type":"item","numeric-id":3670553,"id":"Q3670553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119020$06D62B27-269E-47A3-8753-4900BCC3DD2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f837c623bf58c21b7997511c468a133c0deb27a9","datavalue":{"value":{"entity-type":"item","numeric-id":3778541,"id":"Q3778541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119020$2D7934AE-E8FA-4EB4-9C96-D2A0F3CAEC07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26736971b71f38c87ce58e186943954df95eb066","datavalue":{"value":{"entity-type":"item","numeric-id":1837617,"id":"Q1837617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119020$49274FF1-8A1A-4F17-BE27-91575D49E31E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b053a1bf81533db47bd102598a3f1c15840b5589","datavalue":{"value":{"entity-type":"item","numeric-id":1079817,"id":"Q1079817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1119020$FA5BDCB5-BC5C-4565-BBE4-B7310C57BD46","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da5c4ac59df90023e1d51c5181501eba12158f92","datavalue":{"value":{"entity-type":"item","numeric-id":492284,"id":"Q492284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"764ee9578f30490264535ee2df708f953cc58b0b","datavalue":{"value":{"amount":"+0.8310621380805969","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":"Q1119020$C7D8E85B-2600-4E57-AC62-717EB77D8F3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab1deca070bcea75847d550d6d4bf0357de85111","datavalue":{"value":{"entity-type":"item","numeric-id":1101685,"id":"Q1101685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"118ffbcaca80848f590a72bf05e4772d6203b8f5","datavalue":{"value":{"amount":"+0.824374794960022","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":"Q1119020$7FC8810A-ACF7-489A-A224-159EF0D53061","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78bdf707df3928faba2ee98d2b43ed70af39f550","datavalue":{"value":{"entity-type":"item","numeric-id":674178,"id":"Q674178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad990e22aa3a77404ec204baf25e160cf27847a4","datavalue":{"value":{"amount":"+0.8186914324760437","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":"Q1119020$72FBAA8D-3859-4D41-90F8-E68B6C7ECFD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"785cfa4c42e2c0be5563ecc904cfd122c68207bc","datavalue":{"value":{"entity-type":"item","numeric-id":4763415,"id":"Q4763415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56c49f70d3d927aa0fd248f172384b5fb0018f8d","datavalue":{"value":{"amount":"+0.8159741163253784","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":"Q1119020$817E3ED3-B7E1-4E79-B927-E705CACCD5C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27856f05567559b076501b66f1092d34fd5ea04a","datavalue":{"value":{"entity-type":"item","numeric-id":3373055,"id":"Q3373055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90c97ba80950a3a5349e532278e9afb7af8bf5ce","datavalue":{"value":{"amount":"+0.8152293562889099","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":"Q1119020$517E94EE-6575-4A41-A019-E55C36A2632A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of polyhedral separability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_complexity_of_polyhedral_separability"}}}}}