{"entities":{"Q5952927":{"pageid":8129729,"ns":120,"title":"Item:Q5952927","lastrevid":47723638,"modified":"2026-01-02T13:04:41Z","type":"item","id":"Q5952927","labels":{"en":{"language":"en","value":"The fundamental class of a rational space, the graph coloring problem and other classical decision problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1690570"}},"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":"Q5952927$D0521AFC-F2A3-48CC-BAA3-68328B8235F3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"070cd7c034e7570b3d6ef378464c9f0cbcd3cb30","datavalue":{"value":{"text":"The fundamental class of a rational space, the graph coloring problem and other classical decision problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5952927$5EF0B777-9F3E-4E8E-814C-00F88D1329CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"32747dc80426788743b0d17599923addf109204d","datavalue":{"value":"0987.55012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5952927$A536597E-606C-4A86-B793-B7C326DB8412","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98f62f11df0b4c13c1af04031dae8be2a787a3c3","datavalue":{"value":{"entity-type":"item","numeric-id":223860,"id":"Q223860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5952927$A2F8A5C3-E14B-4CFB-AB3E-0109377F46EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e289773591fb8f77a7d7277f13064aa77a1cd618","datavalue":{"value":{"entity-type":"item","numeric-id":1382062,"id":"Q1382062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5952927$AEE17A49-33BA-4CB0-BB61-FA39D3CC3CCC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c4f16ddc5cdb18d4f4fb3ee6d704d6609c3404ba","datavalue":{"value":{"entity-type":"item","numeric-id":223802,"id":"Q223802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5952927$6E1C76E3-0C34-4739-9560-BF6FA3F1D70C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4c27c7c0f05a747a24a0ab4d7e53da6cd04b7e8f","datavalue":{"value":{"time":"+2002-06-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5952927$5542F9FA-A522-4F82-8288-CE749A2FD71E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f16c48936c2b8c033befe9f65cb9f1aae0e6f4e2","datavalue":{"value":"It is possible to associate to a graph \\(G\\) and any integer \\(k > 2\\) a rational space \\(S_{G,K}\\) whose minimal model is generated by the vertices and edges situated in appropriate dimensions. The authors have shown earlier [Topology 39, No. 1, 89-94 (2000; Zbl 0933.55014)] that \\(G\\) is \\(k\\)-colorable iff the singular cohomology of \\(S_{G,K}\\) with rational coefficients is infinite dimensional. In this paper they describe an alternative view of this phenomenon. In the cohomology of \\(S_{G,K}\\) one can define a class, whose nonvanishing implies that the cohomology is finite. The authors give a new construction of this class, for which it is possible to produce a representative in polynomial time. The authors draw a number of conclusions on the NP-hardness of problems in the computation of rational homology classes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5952927$0308FCD3-42D0-4818-947F-FDE38B01FF42","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"073034c111734685a386a9ec1a39b197886ab678","datavalue":{"value":{"entity-type":"item","numeric-id":1235431,"id":"Q1235431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5952927$AD7D294D-435B-4A0E-94D4-77D036817F67","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9c2f67869d26c9dc70339f9cc33416aff4c4771b","datavalue":{"value":"55P62","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5952927$6BD193CB-7ECC-4BB8-BFD7-4AE5F7EBF2E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5952927$07F986D9-274A-4799-8572-538863194213","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5952927$ED47DA32-2AC2-4B84-BC56-760858B35E81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5952927$F97D138A-9FE3-470C-BC98-7BFBF76D7A15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3681cdd52b2427555b67da80f16c69a7d91cef32","datavalue":{"value":"1690570","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5952927$EA36F818-8CCA-42CD-A09A-DD39D489D2C5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79ee70d94835a9e7233326b2f4f1775c97771b53","datavalue":{"value":"k-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5952927$0B61BAA6-98D9-4C76-8E6A-020406F70D67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q5952927$826D509C-2D8F-4AF9-93D2-25250FCA6056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b7d8902b90d8450c655e01566c21de99bc3a5cf","datavalue":{"value":"rational homotopy","type":"string"},"datatype":"string"},"type":"statement","id":"Q5952927$02D50DE4-FBA6-46B0-B58B-D353D27104F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e7556ca6450b3628d8d482d012cb451d67985f3d","datavalue":{"value":"Sullivan model","type":"string"},"datatype":"string"},"type":"statement","id":"Q5952927$1FC81E71-2C1E-4798-9476-9CDCD05239E7","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":"Q5952927$F8F688AA-0A2B-4E88-9130-CE329E4F5BE5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3929cd1e71ab9c572834c7d360936e7be7c24522","datavalue":{"value":{"entity-type":"item","numeric-id":1806114,"id":"Q1806114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e9df52bd8e738ae40417f568f87999e4db60ed","datavalue":{"value":{"amount":"+0.8578808903694153","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":"Q5952927$A2CEA7F0-577F-41C1-B261-72B0D8527F40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64e07eaff629380fc5becdd96587f95afcaee6bd","datavalue":{"value":{"entity-type":"item","numeric-id":1398203,"id":"Q1398203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e9df52bd8e738ae40417f568f87999e4db60ed","datavalue":{"value":{"amount":"+0.8578808903694153","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":"Q5952927$B70795ED-9BF1-484A-B920-601EBC4CA58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"479f1721322e67b57632bbdeb56849a1c0c1b798","datavalue":{"value":{"entity-type":"item","numeric-id":2352521,"id":"Q2352521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"44f6d7db176ae0f7da0a90d706f8c01e61ecdabe","datavalue":{"value":{"amount":"+0.803376317024231","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":"Q5952927$6DB6978D-D36D-48B4-8276-338322B2507F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c700f480a40d8da4ded4db169d043d8a51fea8a","datavalue":{"value":{"entity-type":"item","numeric-id":1192946,"id":"Q1192946"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0a85b369986964d3673a24c23563764ae2c070f","datavalue":{"value":{"amount":"+0.7818707823753357","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":"Q5952927$BF4138E7-AA6F-4B16-AC02-4C1107D2FAA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06c63156b13976bba51d732cf7cf83497a467cdd","datavalue":{"value":{"entity-type":"item","numeric-id":3805463,"id":"Q3805463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c78290869fa413c3b01447f9bea6718e77e31c85","datavalue":{"value":{"amount":"+0.7475775480270386","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":"Q5952927$6F70B2E0-E1F4-43A1-9077-69D7CC8C563D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5952927","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5952927"}}}}}