{"entities":{"Q5111132":{"pageid":7140706,"ns":120,"title":"Item:Q5111132","lastrevid":91367474,"modified":"2026-06-04T22:59:37Z","type":"item","id":"Q5111132","labels":{"en":{"language":"en","value":"Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gr\u00f6bner bases"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7204253"}},"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":"Q5111132$A2EBF82F-3976-47CD-87F3-EED9E383E972","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"38136720309f065762fbd933140b02ab5e763eca","datavalue":{"value":"1440.68105","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5111132$8C0FD75B-7F61-498F-A120-8D7802C6F366","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a68b55be2ece07cb26d32f7d1e491763db7999e1","datavalue":{"value":{"entity-type":"item","numeric-id":930902,"id":"Q930902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5111132$64A31DD9-C4EA-41D2-AA35-F094F8D58957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7ade4990ab7a79bdd900e48d3fab8c751fcf8949","datavalue":{"value":{"entity-type":"item","numeric-id":989568,"id":"Q989568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5111132$C359676A-675C-49CE-A0F5-463D3D92E07B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"600d3a19753cf6cba81b7e42b63413a76fa78ab3","datavalue":{"value":{"time":"+2020-05-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5111132$A5B5FC7D-0D6C-428D-AFC2-B6078DE7E6EE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5111132$A69B62DF-FCE2-4F36-A91C-947BC434E3C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ece9b879f80d96e2a1d45b28bdcc8cfa6b01861e","datavalue":{"value":"03F20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5111132$87386D4D-72E0-4C4E-BE7D-9952F6A28F57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5111132$9560F2D7-71A0-4B73-AB68-E9CCB77F6AA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"173b0c3afec7c4f9f987722665cc7bdb6b8f5813","datavalue":{"value":"13P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5111132$BBDE3135-4F45-48EB-B7A0-48CD50F7AAA1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"76564c9eabd28f7ba91628b8168e10686e1d3952","datavalue":{"value":"7204253","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5111132$4D613535-BD0A-4B65-A7D5-EDC8B51BFBCA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"986e975208b070c5142b42b7967bb38dc4fad0f4","datavalue":{"value":"proof complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5111132$7E2CD82A-D93E-42D6-8E60-CA3A9B346883","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"393ea5959b60028dd155de81a4c97d51567f82f7","datavalue":{"value":"Nullstellensatz","type":"string"},"datatype":"string"},"type":"statement","id":"Q5111132$B5336C41-917D-4A8B-B542-5383756EB3C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bae09195fd611bccf15c25e209f2742706bae66d","datavalue":{"value":"Gr\u00f6bner basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q5111132$E00E3953-74D2-4766-9882-36C7D14F47C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"211f3c345d1c27387d231726f7e79d65298863cc","datavalue":{"value":"polynomial calculus","type":"string"},"datatype":"string"},"type":"statement","id":"Q5111132$523B0916-384B-4C50-B89B-8F816FCE947D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be3f5c88d3db777a4bdd3348a5d62b7e04a937f6","datavalue":{"value":"cutting planes","type":"string"},"datatype":"string"},"type":"statement","id":"Q5111132$C744C357-77E4-4E0D-B4E9-ED378A3470D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec22a231a95ef8db562e76401f5c81dda99b1a07","datavalue":{"value":"3-colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5111132$DF41265B-3241-449E-A639-26D4BA36E4F5","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"478f9061f14e098e3fdf3fe3667d3a7084c42e61","datavalue":{"value":{"entity-type":"item","numeric-id":18982,"id":"Q18982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5111132$7A7D3C6C-F510-43BA-AFE3-D902273E6DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"9b26b779cc09e21207a69b2ce242c136f84aa5db","datavalue":{"value":{"entity-type":"item","numeric-id":19328,"id":"Q19328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5111132$7A6AB128-EE2A-4270-92C8-AC5BB68AB82B","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":"Q5111132$1F85062F-F0AF-4B43-8082-5DF3BFA2D259","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ac9339f14e45f9169ec2ee6b899acef0c7c8c57a","datavalue":{"value":"10.4230/LIPICS.CCC.2017.2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5111132$9BE89F74-34D4-4175-9777-954ADAA9E7E9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b4f750b0d94445415c88d181cf9ae1b370b081b","datavalue":{"value":{"entity-type":"item","numeric-id":1711835,"id":"Q1711835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f66d12df444cba2862f74b557d51f5410865309","datavalue":{"value":{"amount":"+0.8737707138061523","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":"Q5111132$5E0B32BF-ECDF-4DE3-9CD6-773D88B9F93C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebb7f96de630c607785f217e0da6fca243280600","datavalue":{"value":{"entity-type":"item","numeric-id":2819750,"id":"Q2819750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"329af6066acfda52b2222a18709d4be3120cd93a","datavalue":{"value":{"amount":"+0.8522694706916809","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":"Q5111132$7FEB8296-AD6F-486D-98B7-9B11006CFD59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"441416c8d61a70b566794b47705802e4326c642f","datavalue":{"value":{"entity-type":"item","numeric-id":3552513,"id":"Q3552513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e3b3d15977a4c2928ce6be5e733bb90ceff046d","datavalue":{"value":{"amount":"+0.827129065990448","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":"Q5111132$B5E5BFC3-5878-463A-BAC2-D72B53A8ADD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ca2f9b5bd991eca2ad9d39899604c5b311fc32d","datavalue":{"value":{"entity-type":"item","numeric-id":5301623,"id":"Q5301623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e9801837df01b0455f59cbf31836165d0cdf303","datavalue":{"value":{"amount":"+0.8266475200653076","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":"Q5111132$9D743F52-D56C-412E-87DD-95BEAA37A792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92b2ea1248f4237dfd3ef015257fa8970c415085","datavalue":{"value":{"entity-type":"item","numeric-id":650840,"id":"Q650840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c64f7cd81bcabaea0130883e407a4b085355f768","datavalue":{"value":{"amount":"+0.8254494071006775","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":"Q5111132$E6D852B3-7289-4B09-93AA-EB34081D327D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph colouring is hard for algorithms based on Hilbert's Nullstellensatz and Gr\u00f6bner bases","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_colouring_is_hard_for_algorithms_based_on_Hilbert%27s_Nullstellensatz_and_Gr%C3%B6bner_bases"}}}}}