{"entities":{"Q805625":{"pageid":807473,"ns":120,"title":"Item:Q805625","lastrevid":49513297,"modified":"2026-01-07T10:41:40Z","type":"item","id":"Q805625","labels":{"en":{"language":"en","value":"Planar graph coloring is not self-reducible, assuming P\\(\\neq NP\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4204366"}},"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":"Q805625$FC948E2B-200A-42E0-8269-326B191AF72E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a588ec68d1be037d9e303c618b6a214d207aea99","datavalue":{"value":{"text":"Planar graph coloring is not self-reducible, assuming P\\(\\neq NP\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q805625$2AE731AF-D7F4-4B6B-91FF-E119A90F5A52","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ef6d52e658e40c5170d9977c7d983b734a9f56b0","datavalue":{"value":"0729.05019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805625$2B372887-700D-4E30-8F2C-78703D7DA07F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ddf6dc2fe35c3f8db20c64d5b3bea9aeda779ba0","datavalue":{"value":"10.1016/0304-3975(91)90081-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805625$A33941AA-B1E9-42E4-963B-B492B922ED1E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f496316b317a1071c5b5dfba5a175583d61d254d","datavalue":{"value":{"entity-type":"item","numeric-id":194031,"id":"Q194031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805625$746C2F89-92EC-40B9-929B-1FD1D0B6AE9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d60cc394e2e4fe5c30e46e2359ff881fbae889f7","datavalue":{"value":{"entity-type":"item","numeric-id":593777,"id":"Q593777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805625$BE8D3779-F772-4870-865F-6D02786CB42B","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":"Q805625$1E7F1E88-276B-438D-A2E1-E6A2FCBED116","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q805625$7DA4DD82-F5DD-4B7A-A0DD-621A5F01D052","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805625$84430139-31D7-48D2-968C-829AE4F5A69A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805625$2586004F-9A8F-44C2-80F6-A86FA006C762","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805625$F6469DE6-F1C2-403B-811D-8F344FB8C01C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"18b5afd18e89ddd43db1bbd52bc4598248260ad2","datavalue":{"value":"4204366","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805625$F80D7600-3EBD-46D5-9B1C-DCCB6683C398","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q805625$7BE8535E-AA0B-4F7B-A825-32022B688783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6348dbfe9a57333476707b2506d157bb02d19748","datavalue":{"value":"planar graph four-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q805625$02A1AE9A-C606-4020-8EE4-BC9AED9C7016","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":"Q805625$831D3E86-EC76-4FFB-BD48-609A4C74C3BB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"86187cd049bd6565ddbc4e21f37dc55f378bee76","datavalue":{"value":{"entity-type":"item","numeric-id":1250223,"id":"Q1250223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805625$E88CBEFC-AA96-4CDA-A933-AD23B6F7BD5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65d73ae8ce50631a13a2e25599a048bc2eda73","datavalue":{"value":{"entity-type":"item","numeric-id":4158479,"id":"Q4158479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805625$9CABC7E3-6E67-4CE3-B810-55955730152B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7678cadff422dc18fb5c6f9d2c4055e1ab7c4be8","datavalue":{"value":{"entity-type":"item","numeric-id":1079379,"id":"Q1079379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805625$342DEBB7-CBDA-4A6E-BA08-C89A9B75EAD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cacefeedbc112be8dbe48f89e8cd3c176bb87a52","datavalue":{"value":{"entity-type":"item","numeric-id":3816974,"id":"Q3816974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805625$683D1418-8747-49B4-8B9E-67F447269DB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76d17cdc84d5a7c88fde84de7f32f71667e04184","datavalue":{"value":{"entity-type":"item","numeric-id":5470709,"id":"Q5470709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q805625$0A880803-B526-46E3-B24E-14E4717F4F8A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1dd5c5220b1e09da3ce571d169e91e98d42350d5","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90081-c","type":"string"},"datatype":"url"},"type":"statement","id":"Q805625$2C6B6D21-E623-4729-B7DB-0CD1ED5D3ED6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aca5abd700e454430e7c11ff130034b8a49742dc","datavalue":{"value":"W2087358907","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q805625$2DD8BE6F-C4A1-4DFA-B227-BCFFF09E85D2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"850e911bd6f425f4016afe44050097c211dd8428","datavalue":{"value":{"entity-type":"item","numeric-id":845727,"id":"Q845727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6611b7200115a63220de3ad77485abf671f67b09","datavalue":{"value":{"amount":"+0.9166678786277772","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":"Q805625$31AC6302-1296-433F-8B56-3B5D6D6E3D50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48d48cb8672732ec5462c00c554ed43f72ee24c3","datavalue":{"value":{"entity-type":"item","numeric-id":4448375,"id":"Q4448375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c7e08288adf8b31fa8be82db81f4edcf0839d15","datavalue":{"value":{"amount":"+0.8000174760818481","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":"Q805625$56B2003F-2B2F-4827-A3C6-D9EEE7343B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97147aae21537631ca1b904e4eadf6873ec7b909","datavalue":{"value":{"entity-type":"item","numeric-id":4652619,"id":"Q4652619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f01cbe9aa34b566e209544e392f33d6c0a1d1228","datavalue":{"value":{"amount":"+0.7868324518203735","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":"Q805625$A40F9264-6D6F-46CE-8ABC-86161A232823","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09ba7f1926c8987d3181b45ed3709dbc321b81ff","datavalue":{"value":{"entity-type":"item","numeric-id":596079,"id":"Q596079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73443588d80def02a6b792e6150668fef7b24a3e","datavalue":{"value":{"amount":"+0.7846083045005798","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":"Q805625$473D6087-95F4-44F7-BE07-0AA286E3B09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9dcb85816635ef3524ade90f1abab512feeca9e0","datavalue":{"value":{"entity-type":"item","numeric-id":974757,"id":"Q974757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4977abdd9d5edda20ec3b13696fdc9c4288fb50d","datavalue":{"value":{"amount":"+0.7772819399833679","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":"Q805625$0B88F4BC-069F-478F-A4AF-158ED6687103","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:805625","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:805625"}}}}}