{"entities":{"Q3374757":{"pageid":3385461,"ns":120,"title":"Item:Q3374757","lastrevid":58158681,"modified":"2026-04-04T01:18:49Z","type":"item","id":"Q3374757","labels":{"en":{"language":"en","value":"Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5008975"}},"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":"Q3374757$1A9CF7C8-28CD-47E8-A419-EFDBD6600F35","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"42b8b0eaf00b0aa2bbdbd120d08c88c50f5af2eb","datavalue":{"value":{"text":"Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3374757$774778F5-3501-4164-A971-96A07A586FAC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eb8d92d2e8d728208b2cf234bba779f985d0c13f","datavalue":{"value":"1085.68056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3374757$7EA393E9-26E7-48C8-B401-1659E1FAF4A7","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":"Q3374757$97BA2749-CED3-4A8D-ADE0-E0FE9675B3F4","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":"Q3374757$10B0DF40-FB8E-4103-A1AE-98DA388327FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a5e3ebd76102649dda56881ce7835021c87c5250","datavalue":{"value":{"entity-type":"item","numeric-id":693071,"id":"Q693071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$1BBAA303-4EA0-436E-AE85-8CBF06212A9E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cb11a7d64aa2e2ac6f5f0a641dfeb8e0525b889d","datavalue":{"value":{"entity-type":"item","numeric-id":2720405,"id":"Q2720405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$A624D618-0C29-4CD8-8055-5BE5F84B2691","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"462aec8569e52448f10bc239db9e6cd6e5e501c8","datavalue":{"value":{"time":"+2006-02-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3374757$B95A8E71-83B3-434C-A9CA-36F29CDC47AF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"26e6307f85e754e0b520495b50655e41ab05e886","datavalue":{"value":"https://arxiv.org/abs/cs/0110025","type":"string"},"datatype":"url"},"type":"statement","id":"Q3374757$46426548-6CAC-412A-AF51-951BEB08A169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"cb1f748c58b3787b6226cb02284db1c14c65b7be","datavalue":{"value":"http://www.numdam.org/item?id=ITA_2006__40_1_75_0","type":"string"},"datatype":"url"},"type":"statement","id":"Q3374757$E6304564-ECD0-45F6-BB3F-800D43EF392E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"0c7d4a05236d6ef9ad9ecc64a2cf4015f5e16602","datavalue":{"value":"https://eudml.org/doc/92790","type":"string"},"datatype":"url"},"type":"statement","id":"Q3374757$1F5DE7B0-51DB-4419-8508-B47F18F70ED5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3374757$0E052E47-EF13-46C5-8917-BFDC1C7898DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3374757$6B729EBE-26C7-494B-90DB-B983841DD595","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3374757$53EE7819-5691-45D9-AA47-DC0A92D4E33A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5ae60abaac11d6efcba6c7d00fe616eeb18ef2cc","datavalue":{"value":"5008975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3374757$76D572F0-8AA7-49C5-ACC0-27D917898E17","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":"Q3374757$D132AB63-A995-4841-A089-92E732C3AE1A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"edb7b79b524fc0ae260ea8c01a7bbc151b888887","datavalue":{"value":"W2569714044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3374757$3262E07B-C86B-4309-835B-707658209170","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":"Q3374757$3B8CE09B-13CB-47D8-91B1-14855EC1EA01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a80eed9f379f185c9ca92aab1fa2ad3cc4463c9","datavalue":{"value":{"entity-type":"item","numeric-id":3887227,"id":"Q3887227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$064D2FDD-98F0-4AF5-9A0A-6D4FD99AE058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"783f5b77f65178466163307ca17329fb72140e4a","datavalue":{"value":{"entity-type":"item","numeric-id":3158517,"id":"Q3158517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$12D15410-E1C6-4BBD-9675-1FE8A4358A71","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":"Q3374757$9DC07E59-7FC4-45D8-8C72-279655180204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dfd9e4996ea3da2d0e02a61f9b6de58e2593e33","datavalue":{"value":{"entity-type":"item","numeric-id":4040797,"id":"Q4040797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$2D8A9DDA-7A24-4C40-B32B-B5E1A8ECFCA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80da5dbf79d1c137536de30a44e307449b537460","datavalue":{"value":{"entity-type":"item","numeric-id":584250,"id":"Q584250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$6E828DDC-667A-4C72-990C-CC4FFF3B4677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6c8c7cd04323f105613807d7c24f994f4cde8bf","datavalue":{"value":{"entity-type":"item","numeric-id":4536344,"id":"Q4536344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$7CB8C9E7-604E-4E43-AAE3-0E1FD7293C72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b9c8f9734cf344f6f5a5b66885892b9dc29edda","datavalue":{"value":{"entity-type":"item","numeric-id":4208875,"id":"Q4208875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$E22E084A-0E22-4141-9EAE-8A79AA432670","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":"Q3374757$5ACBC8F0-B6E3-4CB3-8B41-9C84B12491EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66494da13b766229db19f925c231330da84115bd","datavalue":{"value":{"entity-type":"item","numeric-id":817813,"id":"Q817813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$6287BAE1-4397-4944-A204-769A04968C4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51fe0a06c9cac8bd777910204e90fa3b76a62bba","datavalue":{"value":{"entity-type":"item","numeric-id":4785629,"id":"Q4785629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$F0B13F82-E52F-49F8-95E5-FF7F39F7034D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$89339064-32C9-452A-BA75-F163DAE12792","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb9e97bb808371a3a6d9a49a0700ca457fcb589c","datavalue":{"value":{"entity-type":"item","numeric-id":908700,"id":"Q908700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$BE7C7382-2BB4-4C91-BF29-85F996DACC5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30f6e432ce9e9ae75031144ac1199e0b83ca0d7","datavalue":{"value":{"entity-type":"item","numeric-id":1107309,"id":"Q1107309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$A5469DEF-5C99-49DB-8090-01B5CFA88692","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":"Q3374757$C1B53F77-3D53-4452-B957-C7297409CEB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db3468346fcce29d2fe703e3816d1c0ffadbf3a","datavalue":{"value":{"entity-type":"item","numeric-id":1224109,"id":"Q1224109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$DD9A40EE-C2E1-41E7-BA9E-87D3607BAA18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e956899ee0a7e06c94f20261b5948e49f9acb5d8","datavalue":{"value":{"entity-type":"item","numeric-id":4323730,"id":"Q4323730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$32592C04-8AF0-409A-8A96-71AEA65E7F6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$CC2F3842-9001-446D-B713-D0458035B9E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad86ed10f9dbc91aef6fdb78e5f6edf0ab2f5e6","datavalue":{"value":{"entity-type":"item","numeric-id":4739657,"id":"Q4739657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$CC5A3F46-56CC-4176-AD85-428204F317B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53e31dd483387e2770ec0ec431458678950cd036","datavalue":{"value":{"entity-type":"item","numeric-id":4743737,"id":"Q4743737"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$D1EA8259-F38D-478B-8784-830DCDA8E93D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39f4d9330be6faec531fb339b9586c4c7884698d","datavalue":{"value":{"entity-type":"item","numeric-id":2509032,"id":"Q2509032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$7080A449-81ED-4C28-B100-A4F86CE0BCBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a979f87dc4e09f514e168d506541cad059c53497","datavalue":{"value":{"entity-type":"item","numeric-id":1405784,"id":"Q1405784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$B283A7C7-C934-4164-A2F6-322BE323F5C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6ce05406fb3c4dfaccade1b1601834df8b17439","datavalue":{"value":{"entity-type":"item","numeric-id":4472458,"id":"Q4472458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3374757$5CEABB02-0EB9-4BFC-9478-02E0FED33A5C","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":"Q3374757$D41F7B31-4EA0-4511-A433-8233892010F9","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":"Q3374757$C2C68289-F076-427B-B49B-1981789AA6F6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8d72a2543e45be6148a3831092cec54c9e13b7ec","datavalue":{"value":"10.1051/ITA:2005041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3374757$F26878AD-093F-4948-AC40-24B72DF7BAD7","rank":"normal"}],"P1643":[{"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":"ad27f64f8129c6dbd342558ecf9ac94ee6c2d3bd","datavalue":{"value":{"amount":"+0.9992616772651672","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":"Q3374757$5C2A35FC-3D04-4FDA-8C7B-3EC063EDEB65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f17b98d0087d33ae7c5ca3c4818d07b3d1c7d42","datavalue":{"value":{"entity-type":"item","numeric-id":3971267,"id":"Q3971267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a25a6bdaacf2cc327f01c77bb27480bae17cb1b","datavalue":{"value":{"amount":"+0.8055746555328369","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":"Q3374757$7266D714-5E79-4EC2-B454-7C0D76760DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ef715061fb9af0b567f00940891b8fff8af4a0e","datavalue":{"value":{"entity-type":"item","numeric-id":1328583,"id":"Q1328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"583b5cfc051ef467d3ac1968efac325f9da7735c","datavalue":{"value":{"amount":"+0.8050459027290344","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":"Q3374757$72ACB472-765C-4703-A56E-46FB6CE72D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78bce87af8d73d4ca873664dde72e91154f3aeb7","datavalue":{"value":{"entity-type":"item","numeric-id":293222,"id":"Q293222"},"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":"Q3374757$30300041-ED27-47A7-8E18-6B00F3F1D64C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"590e50ab988b329ad236b6da13d015f03a30fb2e","datavalue":{"value":{"entity-type":"item","numeric-id":2643795,"id":"Q2643795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d50d63fb26a54ef4f8e216ca9dbbaa4342b6e2a7","datavalue":{"value":{"amount":"+0.7692977786064148","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":"Q3374757$0E044009-5E76-4855-887E-1E5273451928","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3374757","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3374757"}}}}}