{"entities":{"Q4999425":{"pageid":7029002,"ns":120,"title":"Item:Q4999425","lastrevid":54039518,"modified":"2026-01-26T03:42:22Z","type":"item","id":"Q4999425","labels":{"en":{"language":"en","value":"Reducibility among combinatorial problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7368884"}},"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":"Q4999425$2B5BD669-F05C-4AA6-A597-19898F4A84FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b5fb95a174ebb0c0cb0ed2c0989baac876061f92","datavalue":{"value":{"text":"Reducibility among Combinatorial Problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4999425$43E526F8-A581-49FC-BB27-E3A02D051E6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e581f7a8d765ce1dd2aa232e4f5cb718f16b16ad","datavalue":{"value":"1467.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$E71820F7-47DA-4553-A117-8CB1BBF8D4B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8dfa4416bbe40cd2c3b7e97ca4572b70b40be8f9","datavalue":{"value":"10.1007/978-1-4684-2001-2_9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$AED5CFA3-EE83-4E0D-B62D-8AA616CAF4E2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"558cd6e0ead38ab851e8691459b59db52f07d583","datavalue":{"value":{"entity-type":"item","numeric-id":4999415,"id":"Q4999415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4999425$AEFC0CDD-4F77-401D-AB53-487D7F02C917","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dea07e2e14cf0a66355cfc6e3cc2a283124ee993","datavalue":{"value":{"time":"+2021-07-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4999425$2989EF01-87AD-4E0A-AA1E-1BD87D3941EF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$316E0787-96A8-4EC1-8F57-20E09EF9D1DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7c4d23e479455dfbfef69cdefa2e2eb3970b9f40","datavalue":{"value":"68Q04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$01CFB14A-5E87-478D-8A23-03CBDE5F80FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$7751D076-E9B4-4547-B421-96CB8E077283","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1397c7d07b55282862d4db12cbe94becf8137559","datavalue":{"value":"68Rxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$A08B9BB7-DE63-4164-9FC9-93A9C4583599","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0224770851afa6088478456cdd393dbdf556a0e1","datavalue":{"value":"7368884","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$0649D2EA-BA28-42F2-8C3D-473826F740AB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q4999425$6AD23F77-87A9-469D-B26A-29424ED40981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q4999425$91F42279-1C3C-4101-A7DB-CF02C9268AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4369065edf6d8d2db82064ebbf82bc692ed5b6f","datavalue":{"value":"regular expression","type":"string"},"datatype":"string"},"type":"statement","id":"Q4999425$6DE4C3FD-240C-45CE-A59B-7A79A29E276B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"433ffe1f87d371a0c15a95e8262a89da6324e8cb","datavalue":{"value":"combinatorial problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q4999425$5714D655-637B-4D97-B888-0C4E6CCCAFD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"744721039f0bb4ff9a7f4794ba121645ec3a653a","datavalue":{"value":"words over a finite alphabet","type":"string"},"datatype":"string"},"type":"statement","id":"Q4999425$F232E5D9-9A82-4207-85AE-625AC07440F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bfbfb7d4a5114622e49017a4cf5d34844b21acd8","datavalue":{"value":"language recognition","type":"string"},"datatype":"string"},"type":"statement","id":"Q4999425$26EE61E2-1BC6-40A9-AFA6-D3D69E474113","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"39d3fbac4ba81f0c691ff1846f155bd8e3bf121f","datavalue":{"value":"Q110971675","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$B4C3C936-7C85-4944-9849-9B747DCF1834","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7f03cf6abbdf2fe79063aacbf005af333537b97","datavalue":{"value":{"entity-type":"item","numeric-id":619905,"id":"Q619905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4999425$4CE17053-FE0B-4482-81C1-0923672B33EC","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":"Q4999425$164C2FF6-C773-4C5A-BD35-1A68FF03FA08","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8f0d1f54010e5f392cb330cf7a6119a9bb792066","datavalue":{"value":"https://doi.org/10.1007/978-1-4684-2001-2_9","type":"string"},"datatype":"url"},"type":"statement","id":"Q4999425$3A860FAB-3506-4407-B617-61B3CDA11809","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"92dabd764ca946d249e56cce94dfce480469d731","datavalue":{"value":"W2401610261","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4999425$9B7A851E-3A63-47E0-AA9D-515AC7E0DE45","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d85c563e00af7f96e12503e4bd175e5b3be75f37","datavalue":{"value":{"entity-type":"item","numeric-id":3565237,"id":"Q3565237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e158444103574d07569a58327453620fce5f9c5","datavalue":{"value":{"amount":"+0.8407358527183533","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":"Q4999425$D0D44887-B648-4869-96BF-D08648EC3EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df684ab8201b649acc8d339dca420dbf8bf70615","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8408277ac9dd06c7b51418123b3f2d5de7fd4db5","datavalue":{"value":{"amount":"+0.8003599047660828","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":"Q4999425$DE8D61CE-005F-4598-AE48-79D8E64C2811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c099a8428eee46ee028aaed59299c0915dd41eb","datavalue":{"value":{"entity-type":"item","numeric-id":3781088,"id":"Q3781088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9457f74cebae6ccc24233b6c3e1ef3f2b479248e","datavalue":{"value":{"amount":"+0.7868237495422363","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":"Q4999425$E4B29AEF-C478-43E0-A9F1-0CC4D451303E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53d2ce91edef86264aa7785e1d92c20dd1f6c139","datavalue":{"value":{"entity-type":"item","numeric-id":3326886,"id":"Q3326886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64df57dbbb15c5e2cabc427429efcc1dfa483eda","datavalue":{"value":{"amount":"+0.7824335694313049","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":"Q4999425$8845CBDA-0151-4C5A-BBA2-ADF6DC169E65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50e321e7e0dc1db5cb67bc1f9f4c12ce4c175859","datavalue":{"value":{"entity-type":"item","numeric-id":4871777,"id":"Q4871777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b9bd27fa0f82ec49c80b882a5e465c769ad367f","datavalue":{"value":{"amount":"+0.7668042778968811","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":"Q4999425$A4243AFF-8BC9-4ED0-AF1A-72C7A53FCB1F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4999425","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4999425"}}}}}