{"entities":{"Q1259902":{"pageid":1270652,"ns":120,"title":"Item:Q1259902","lastrevid":68316129,"modified":"2026-04-12T22:53:20Z","type":"item","id":"Q1259902","labels":{"en":{"language":"en","value":"Graph 2-isomorphism is NP-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3640869"}},"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":"Q1259902$EE6FB04B-4488-48C4-AB5E-D9C869D12837","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1f50305a18e5bfe3916c5bde70e5666d317d5995","datavalue":{"value":{"text":"Graph 2-isomorphism is NP-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1259902$673A2932-ACF8-4BB2-9D84-05AB317550F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9fa211574cbf4a0f73cc07c88ee0879a1c7141e4","datavalue":{"value":"0412.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1259902$9D91BA5D-2808-4A56-8E60-A3011D352C88","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bb313333dca18a8f27964856d99b3ba44d4478dc","datavalue":{"value":"10.1016/0020-0190(79)90130-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1259902$A57F1125-4710-4C05-9E22-68483C1A673D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"588071f50c260cf948e24afbba8472b09c69eb83","datavalue":{"value":{"entity-type":"item","numeric-id":914379,"id":"Q914379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1259902$40C810D4-AE9A-43D9-B477-8DAD059EC039","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":"Q1259902$A701315E-7E4B-4A01-A0D2-4F7081B2F893","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0b87f78dda5694898cc127305eecf88680ce6c83","datavalue":{"value":{"time":"+1979-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1259902$8A1F8C95-C457-4262-A991-5FF1A667F087","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1259902$F4142383-8D6B-427C-A8C4-5FC171ADF07D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb6fa31c061028a10fb1c2a1679af7746583c504","datavalue":{"value":"05B40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1259902$37A3FDB9-A4C5-41B3-9B3E-4FF65135DEAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1259902$DFD1AD7F-1BEC-4EDA-9CD8-2D60A2B8C12C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"62dac9b60a7ae30af055ac5df3b8d4ff37c4a717","datavalue":{"value":"3640869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1259902$75454980-A350-4AC3-93F5-845591092A4E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1259902$0C0225D4-99B8-4057-8169-9DE49111D54B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e0149f11e333f11010670e0e78fa58c70aa2325","datavalue":{"value":"Np-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1259902$7FE29D0E-3828-45AD-8B9F-A7B97F727FC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1259902$11AC243D-D2F8-427F-86F8-9BF74FB35BC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afefb78b68ac9c51876f5017d2796195ef1f190f","datavalue":{"value":"exact cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q1259902$D57F45FA-E1C8-4103-A052-3CA9C278A3F7","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":"Q1259902$83EDDF8D-53F7-46CB-9F34-D53F813B5326","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1f60d82c99887e321cc5f91818800d4acd8957f4","datavalue":{"value":"https://doi.org/10.1016/0020-0190(79)90130-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1259902$8C65F5F0-F6C0-4FE6-9654-3EC68D21DA41","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa3c400dd49b58f9fb3a8b72c5168ec8e52ba9ba","datavalue":{"value":"W2056179367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1259902$5DBC4455-8C42-4016-9E91-F6455EAD695B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"326a2ad7b36ff0c34ee68dee5a1c027d12a45ba0","datavalue":{"value":{"entity-type":"item","numeric-id":3872501,"id":"Q3872501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1259902$3F5C3445-D665-4810-B0F7-3A7D30429E1A","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":"Q1259902$8D61931E-D4AC-4DD4-B37E-CD392C600738","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1259902$214F6A58-B274-41A5-B9E9-D33EE9F7B82A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1259902$042301DB-6732-4E33-B985-F9EEA728CE48","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph 2-isomorphism is NP-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_2-isomorphism_is_NP-complete"}}}}}