{"entities":{"Q1126837":{"pageid":1137586,"ns":120,"title":"Item:Q1126837","lastrevid":66188310,"modified":"2026-04-12T08:08:26Z","type":"item","id":"Q1126837","labels":{"en":{"language":"en","value":"Games, complexity classes, and approximation algorithms."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1184381"}},"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":"Q1126837$C7B5FD04-8E8B-4A11-B208-4602BE09ED4C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"92a4edb1075b9e43b1cc1ff8501df585dacebed7","datavalue":{"value":{"text":"Games, complexity classes, and approximation algorithms.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1126837$582DB155-07DB-4A63-ACFC-DBE58D1564D6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8dece83a807deb2543f3010a400e7ed20a1f4aee","datavalue":{"value":"1034.68521","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126837$A1F19AC5-1C5B-4F73-AD00-33046F010F2A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"59f503b1f6715505f2cac45fa052432796615085","datavalue":{"value":{"entity-type":"item","numeric-id":222779,"id":"Q222779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126837$7C5000A4-261A-478B-9D28-E43287F3BFE8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4add3c5163a5eee9bbe20dc8a36386ab43b68fd6","datavalue":{"value":{"entity-type":"item","numeric-id":168490,"id":"Q168490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126837$7B421875-0187-47B2-ABDF-A306CC3EA3C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0213be50779ba5bffb4613228959545da04beaec","datavalue":{"value":{"time":"+1998-08-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1126837$0F693C53-C1BD-4BE6-B9FD-F4BEC27801C4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"da0f5235c95ec5d0c3b743372d508b7651e9baa3","datavalue":{"value":"https://eudml.org/doc/222677","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126837$E5024EAB-CB88-470C-8F8D-F9FD94FF125F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d70854da6ab3b2290222f8eb3e830275de5278b","datavalue":{"value":"http://www.emis.de/journals/DMJDMV/xvol-icm/14/Feigenbaum.MAN.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126837$0424F7CB-5B31-4D20-B025-16AFA7C640F8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"16ab08150647b310adb25b8747b0db13f13b9777","datavalue":{"value":"Summary: We survey recent results about game-theoretic characterizations of computational complexity classes. We also show how these results are used to prove that certain natural optimization functions are as hard to approximate closely as they are to compute exactly.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126837$65E60ECA-E59A-4961-8DA0-1C1EC45B39D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126837$52A5E00C-77CE-4B58-9748-39FC5C8148AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4782ec55a8b8cc3ebd55f173b4568991ce0fd6ad","datavalue":{"value":"91A99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126837$58F74BBD-5A9B-487F-AF4B-430597ABA026","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d69d177ef5b53f9ffabc0b2e7cdd78efb92b65e9","datavalue":{"value":"1184381","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126837$D029D1A5-15D4-4209-B5ED-761765247EFD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"133967f6c7518bc7da1f1e5db8fbe7b16c1a0f9c","datavalue":{"value":"perfect information","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126837$B28130F5-AA06-4CA9-8456-29AC6E68873F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1631dec4f73456571d2c47ae7e43e83913d9b6b4","datavalue":{"value":"perfect recall","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126837$C02B75ED-03DF-41C2-A171-BA7A7BFE4A21","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":"Q1126837$02F01A76-E440-4E88-BE48-B64BD8F79CDD","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"d9dca07b63ba54a1b7037bfdb3163e690dba9406","datavalue":{"value":"bafkreihkjg3x5ujk5y73lk76jegy2n7mchbkgzit2qs564zmrmxtc75d3m","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126837$71AEA6B8-989A-4F93-A572-B0022083E7BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17225449218f9677a1196e0f02578b62c6a60d6f","datavalue":{"value":{"entity-type":"item","numeric-id":4951047,"id":"Q4951047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e79fec0d9926d5e4af42025e72206cea777a2a7d","datavalue":{"value":{"amount":"+0.9032393","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$5EE3F9A8-D976-4D19-8FAE-EEAF07C54A46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"372545fcc8928eb641c445d33f49ee468cef9536","datavalue":{"value":{"entity-type":"item","numeric-id":3575160,"id":"Q3575160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b224cc66c4321a95f4711e8d54a5985ef28b9965","datavalue":{"value":{"amount":"+0.8922175","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$0EFF5556-C733-4897-994A-3ED5D7B1206E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2babcdef6899ec669f34be7ffe94b05c934fd9cd","datavalue":{"value":{"entity-type":"item","numeric-id":3396628,"id":"Q3396628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2909e8e236115d1cdcf899bed98ea7db22096371","datavalue":{"value":{"amount":"+0.8830553","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$C6E8E8C7-91ED-4171-9683-FCC2F3C3DAE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60968c8b9e76ec731b77eb4bdd8ff458397b0b15","datavalue":{"value":{"entity-type":"item","numeric-id":2934593,"id":"Q2934593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"857820c10f93548a52b032bb6dc19815ca4f004b","datavalue":{"value":{"amount":"+0.88085777","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$40F22241-C904-40C0-8A1D-79577D0DB3A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3410736a0a203dd7dab4f89afa41c77a39b12b1","datavalue":{"value":{"entity-type":"item","numeric-id":1583532,"id":"Q1583532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9524f1653b9bfdc1e20c4e8e4b8bcfad5c368dd8","datavalue":{"value":{"amount":"+0.8771619","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$611C5451-A49D-4611-A3EE-3C07C7A87F3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2155431d92180ab1a6d7a202b90c475351ff75f","datavalue":{"value":{"entity-type":"item","numeric-id":3002794,"id":"Q3002794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da5ff0ab4ea9a79caa693a0ac2eae61792f9f559","datavalue":{"value":{"amount":"+0.876181","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$E882778A-E8D9-48DC-B49F-90C8B835B8F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42b85ef6737dc22749be705815e17f10786c97b6","datavalue":{"value":{"entity-type":"item","numeric-id":3652196,"id":"Q3652196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3477c55a67f2b820517635ada79014aa31f6b66","datavalue":{"value":{"amount":"+0.87204427","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$C0414BBC-9901-4C45-98BB-F4F487344DFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70524b74c6d8900b656e876f2d86752d016115d6","datavalue":{"value":{"entity-type":"item","numeric-id":5492884,"id":"Q5492884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce3d21f8a38915ff28d2f79b3ec001a05f1589ef","datavalue":{"value":{"amount":"+0.87141275","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$26BED66A-AFEC-4B4F-90CD-5C17F1B4A2E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6550aeaa23307f73840e2d678a7c03aab389acc7","datavalue":{"value":{"entity-type":"item","numeric-id":4263796,"id":"Q4263796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc0933855da3dee99a9af26cee567a63d54720e0","datavalue":{"value":{"amount":"+0.8707602","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1126837$6ADBB155-BB9E-4185-8766-B38F40DE7E71","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Games, complexity classes, and approximation algorithms.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Games,_complexity_classes,_and_approximation_algorithms."}}}}}