{"entities":{"Q293222":{"pageid":294989,"ns":120,"title":"Item:Q293222","lastrevid":60797109,"modified":"2026-04-10T19:11:29Z","type":"item","id":"Q293222","labels":{"en":{"language":"en","value":"Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6590681"}},"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":"Q293222$1A976A3B-1A22-45CA-A2D2-8E6BBB58AF69","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9abc1118f4007f51e6dc47eaba4e2e4bfd721ec5","datavalue":{"value":{"text":"Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q293222$85CE0010-B245-4926-8E51-60A7EC25C736","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"74c7e0ec94357a485ded4a7e30ae8176e87e1057","datavalue":{"value":"1338.68087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q293222$F98BCB2A-0EE9-45AC-839A-E9F7998F8019","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1919cbb9ff26856bec623f597e98de49764db803","datavalue":{"value":"10.1016/S0020-0190(97)00219-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q293222$9E73A321-37D0-412A-9B8C-7DDD55262EC4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5f5c67ba04f18de6b92a0e90cb5f04518d29d25","datavalue":{"value":{"entity-type":"item","numeric-id":293221,"id":"Q293221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$D06F9FC4-3323-48FF-8818-427FF9538BDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"813ea56633814b981b20b79c4950ef61f792e6b4","datavalue":{"value":{"entity-type":"item","numeric-id":267647,"id":"Q267647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$28BD2A17-4ADC-49BB-9060-98752827F371","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$5CDC03D5-4FA2-4F63-8AC4-AC8C807FE2A8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c38536433ca3187d3c315e3ccb89d3160798fa7b","datavalue":{"value":{"time":"+2016-06-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q293222$D7BD28EB-9568-43C2-B3FE-35F5E156A521","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c73337f267fc6c30b11f97b7d99308b3f19bfcc1","datavalue":{"value":"http://www.sciencedirect.com/science/article/pii/S0020019097002196?np=y","type":"string"},"datatype":"url"},"type":"statement","id":"Q293222$DA78CF93-7156-434B-9D9B-19003D7E4553","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q293222$1C299CE9-6FE9-4DC7-AD07-78F98D840E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q293222$4B0CBDF9-EE76-454C-B6E2-19DE5B59CF15","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aedb0d6109fc94f59138934f0d63e7b1d3e10c95","datavalue":{"value":"6590681","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q293222$38809145-3D59-452E-9F12-8A137C77F47B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q293222$771BD3F3-44AB-4024-A762-92985E521E71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q293222$A5741984-5567-4ABA-9D95-9A3EDDFFED9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f0c796fe08d1f3c658a7eb37cd1e46a8dbaf0b5","datavalue":{"value":"maximum independent set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q293222$91FF3815-6DBE-45B9-A57B-77E28D68228D","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":"Q293222$FFF9AB66-9967-4195-84C3-836056F5872C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a35f325e188a98215a65a2962cebbaf856a936b5","datavalue":{"value":{"entity-type":"item","numeric-id":286978,"id":"Q286978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$85D8A80D-B8B2-43CF-B554-C6E3AC33296E","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":"Q293222$C77CB50F-EE4C-4546-B976-B641454F5700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4951b82224c1933dca3bed11693b3cc1b8d0c0f4","datavalue":{"value":{"entity-type":"item","numeric-id":2817635,"id":"Q2817635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$C23BB3FB-9C4E-44BB-BAB5-450E546FEFCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"276acf5675c010471dc3fde34dad6463928de402","datavalue":{"value":{"entity-type":"item","numeric-id":293222,"id":"Q293222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$B43DFCE2-B0E5-4956-AD1A-7BC72F567551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b2a1a71b49ec8a49d1aaa20916821b36ece12fa","datavalue":{"value":{"entity-type":"item","numeric-id":3815290,"id":"Q3815290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$335405D0-B266-4333-993E-B9933BCB50AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07b832ae6038bd66626b817aa4f18e62fe9f667e","datavalue":{"value":{"entity-type":"item","numeric-id":3783278,"id":"Q3783278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$F8602494-D01E-4727-8CE2-97221221BD35","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":"Q293222$5678FD4B-E4EA-4056-8FA1-6162EEAA2546","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$90E2F1FB-0F2F-4D78-BF44-F44B5215D874","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"275f6fd096ef2a8f2e6a1f42c55fc3df82f7b230","datavalue":{"value":{"entity-type":"item","numeric-id":1924128,"id":"Q1924128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$0BD3BAF5-D341-494F-A7DE-2BA5AE8B3FCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4d825ccc462d0f4ec55e9d5da8d8afd257e6fab","datavalue":{"value":{"entity-type":"item","numeric-id":1107524,"id":"Q1107524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$3650EEF3-C355-44EC-87FB-C38BB14861B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d1f5d749e4775b9ff8ad70d19f88e3741e680ea","datavalue":{"value":{"entity-type":"item","numeric-id":3495646,"id":"Q3495646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q293222$FF65C481-A9A9-498D-B123-979D6323A18A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b5a487bf900d7d174cdc6410dd9137d9eb98449d","datavalue":{"value":"W2005980753","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q293222$C5CEFB7D-47E3-4209-BDF7-33B43D4EA54F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"047020f3e62a0c9f98bbac259149bd1b2d2a5390","datavalue":{"value":{"entity-type":"item","numeric-id":286978,"id":"Q286978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1fd672472f27c3c572c2a226dbac4a12df277f6d","datavalue":{"value":{"amount":"+0.8303139805793762","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":"Q293222$CB3B8506-6397-43F9-8F63-767C97BC1420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00c4a146f22827368126e86857a991bea23744ff","datavalue":{"value":{"entity-type":"item","numeric-id":4414503,"id":"Q4414503"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec20a7abf4b30bae39012ff56afb4ff8998a7e76","datavalue":{"value":{"amount":"+0.8037327527999878","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":"Q293222$AF7FA0C4-1974-4F3E-8134-459BAC188501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"422447afdd380b2a182801839d4fe06e0822827e","datavalue":{"value":{"entity-type":"item","numeric-id":3374757,"id":"Q3374757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99d539110dacff56539d94181ac4062fee829388","datavalue":{"value":{"amount":"+0.8028287887573242","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":"Q293222$F18B7B63-3F3C-412B-BF23-D96C3FFEF840","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe7bd5af87bfc216857cc3aff614d41d4e397acd","datavalue":{"value":{"entity-type":"item","numeric-id":1184733,"id":"Q1184733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c29cd6edcd563e91696c8a482ad2c99b8b9e1a5","datavalue":{"value":{"amount":"+0.7868607640266418","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":"Q293222$82773E17-8F7C-4F77-8352-5CD2184719D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c234b2dfaa15f5c402022f846a67cacb4825f44b","datavalue":{"value":{"entity-type":"item","numeric-id":5057456,"id":"Q5057456"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62f969d20085d1ac13f78d7b1e9ec8ed0b7b708c","datavalue":{"value":{"amount":"+0.7863020300865173","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":"Q293222$7EC08577-84EA-4A5D-8C7F-1791A61577E8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recognizing when greed can approximate maximum independent sets is complete for parallel access to NP","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recognizing_when_greed_can_approximate_maximum_independent_sets_is_complete_for_parallel_access_to_NP"}}}}}