{"entities":{"Q1185245":{"pageid":1195994,"ns":120,"title":"Item:Q1185245","lastrevid":70762365,"modified":"2026-04-13T16:39:47Z","type":"item","id":"Q1185245","labels":{"en":{"language":"en","value":"Perfect matching for regular graphs is \\(AC^ 0\\)-hard for the general matching problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 37946"}},"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":"Q1185245$4299AA07-72A5-489F-AEEC-8F027D0F9462","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d70a83eb0f008f75f0b9490d1f96916ea55bb0f","datavalue":{"value":{"text":"Perfect matching for regular graphs is \\(AC^ 0\\)-hard for the general matching problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1185245$5BCB134C-F9B3-4374-85F4-6047C15F289E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dbdf5410bfcb61eeff1da2375d6a625bf55360f9","datavalue":{"value":"0743.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185245$0EE97730-92F9-4720-8452-4B5CC8E3116F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e8da3aa0f5e22df73b0c590e35b3fa65d1ec2d21","datavalue":{"value":"10.1016/0022-0000(92)90005-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185245$38BF1FEC-F3A6-4540-8FF8-083AA704B3C7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9d1c5666cfcb8034d94e72905fe0b245c5645906","datavalue":{"value":{"entity-type":"item","numeric-id":233438,"id":"Q233438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$21D68037-3871-4FB7-99EA-526923189BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"572a13162b6df712d7941005f95a34b361dad87b","datavalue":{"value":{"entity-type":"item","numeric-id":396628,"id":"Q396628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$28B9B64A-FD8D-4EE8-B0B9-39B230CD0336","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$1EA72126-639D-41D2-B0E8-0D8B1CA246EA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1185245$3D2657AF-8985-44F2-93F3-69C61E5ED9D3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185245$7A205CD9-3406-4D84-AA51-F36FF4382F83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185245$FFB096AF-0411-4CCE-9818-A820375ABAE8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dd8e3633ca2d029aea4c3d3f00c99a99a91255e9","datavalue":{"value":"37946","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185245$0585F87F-BD36-430A-B59B-EFF85FB9B010","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a63f5fdf3038af45049408a9914d671beb783a5b","datavalue":{"value":"parallel complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185245$9622D25E-E696-4698-B8DC-C63988305DE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82e3dcf147dcf96624cba1720b93f11ecf8216e8","datavalue":{"value":"Peterson's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185245$982FD83F-0A9A-4E0B-8AA5-6E5474F2782A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1185245$D04BA8B0-FD64-4672-B71D-1842068BEFFC","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":"Q1185245$DAD0F301-A020-4FCB-AE9C-0AFCBE60E242","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bc316773ecff5f90072d6990e48613fb93fc3821","datavalue":{"value":"https://doi.org/10.1016/0022-0000(92)90005-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1185245$0F04BFED-5860-4187-A1A7-84C03AD4E94E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f21fb16c6fdf278f14a9773e3ea1aa9a56f35890","datavalue":{"value":"W1964011448","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1185245$9FB86004-FFD4-4ADC-AC75-2D3CA1B77E6D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5899e3e12a743d53573a910fcbfa636f0f6c8e3","datavalue":{"value":{"entity-type":"item","numeric-id":3852212,"id":"Q3852212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$3CD7E94D-B54B-4433-8F23-7EB929D4A878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2a62e0c2c4898eab4647372398f82007b042b16","datavalue":{"value":{"entity-type":"item","numeric-id":4162481,"id":"Q4162481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$F966B797-503A-48C5-A748-826D1D9E9013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$B2357541-2FDE-4F39-9497-EAD0AEB0CDCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0262c7ca9d46cfb4cf3512f2a0333529706ee62","datavalue":{"value":{"entity-type":"item","numeric-id":3684121,"id":"Q3684121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$805E2EEB-FB5D-418F-860E-76DEE572143D","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":"Q1185245$655D8B7C-158C-468B-B9FA-512156A2307A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"720cb0112745e0fc4d414a8652264da0bad7fa31","datavalue":{"value":{"entity-type":"item","numeric-id":3731028,"id":"Q3731028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$E6139C71-FD82-455E-B93D-703ED6786B21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84bbca1bd52a8b705768d2a03b4b5b5c1b7c0d27","datavalue":{"value":{"entity-type":"item","numeric-id":4385522,"id":"Q4385522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$C2E35A36-6C02-48C0-9E8C-B3E157801E7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df683643124679dcd0453572ee8d22f0d31fdfc3","datavalue":{"value":{"entity-type":"item","numeric-id":1115630,"id":"Q1115630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$DC6C8415-B645-4B7A-9872-973D2BCB884F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"310ec4e9bf739fc2741b5a947cedf96624f64247","datavalue":{"value":{"entity-type":"item","numeric-id":3732972,"id":"Q3732972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$1D95B653-416C-43CA-B43E-083F48D3DE09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05f132c6521c12283446aaf341248df05dd5b786","datavalue":{"value":{"entity-type":"item","numeric-id":3904540,"id":"Q3904540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$73928197-A0A3-49A5-A789-80A13CBAD6BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$DFAC08AA-BA55-4EE7-A2A7-F12948509F21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec62482a6f1abfd15d9d0aa6d0ca02f4b7a14835","datavalue":{"value":{"entity-type":"item","numeric-id":1095658,"id":"Q1095658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1185245$EFD3E8C3-6E5A-409A-8F39-44D2538289EF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f8ab01eaa882050260181ff04d2e8b8568bbc13","datavalue":{"value":{"entity-type":"item","numeric-id":2848226,"id":"Q2848226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ab037143c08febb0c157680d1fad18fef6340e6","datavalue":{"value":{"amount":"+0.8861375","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":"Q1185245$8FF0261B-E121-490C-B540-7390400AD7A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e12f82324544d88d68f5d1d32dd42387b2133868","datavalue":{"value":{"entity-type":"item","numeric-id":2875130,"id":"Q2875130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a450e24c8578735d5d73dcf80befd29d392f176","datavalue":{"value":{"amount":"+0.88613737","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":"Q1185245$9976220B-5E14-458B-9C6D-20A413506D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"756eb21d7ac6afaec417269c23d186c28302c16a","datavalue":{"value":{"entity-type":"item","numeric-id":2322505,"id":"Q2322505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d63b876ece55cafb50344777cc3fa069c1fb765c","datavalue":{"value":{"amount":"+0.8820622","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":"Q1185245$B8AE0031-1E04-495D-9A0F-39985FF1D503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"118fdc8b52cd33c567a02e24d7983afabfae491b","datavalue":{"value":{"entity-type":"item","numeric-id":1380203,"id":"Q1380203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5c9fbc0d50efda73d5b6bc97f5ea3cef3568d80","datavalue":{"value":{"amount":"+0.8791771","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":"Q1185245$7178A19C-0CF6-4FD3-9F42-409373D856A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02059901a86ecfad0c7fec9a16edbd3aad777cc7","datavalue":{"value":{"entity-type":"item","numeric-id":299061,"id":"Q299061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed78b27c9ad74454161160e800a2d0bbd881e4b4","datavalue":{"value":{"amount":"+0.87546265","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":"Q1185245$E7B06FD6-1AF9-45DD-82CB-F3F10DC76199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b721ae448419296d14e180ae56723d3ca015dc4c","datavalue":{"value":{"entity-type":"item","numeric-id":659743,"id":"Q659743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e055cc9879c332447b1a29f35e3aa01a11d30ae5","datavalue":{"value":{"amount":"+0.8700814","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":"Q1185245$E49A9BEC-DE8C-4C2D-A50B-54586D04CD4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21456103b756bfd08f0021e386de3264bd704883","datavalue":{"value":{"entity-type":"item","numeric-id":1964595,"id":"Q1964595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2928691e9417d081e2cd42327244be0e340f9721","datavalue":{"value":{"amount":"+0.8660301","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":"Q1185245$88EA9222-CA39-4F4C-88D8-60286AA897A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da544f8ef866ef4de8851886ef1f00d44953969b","datavalue":{"value":{"entity-type":"item","numeric-id":4973885,"id":"Q4973885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"547d1d9ff937c10ad38de10d9666afb071081efe","datavalue":{"value":{"amount":"+0.86529136","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":"Q1185245$30026C91-A1B2-4352-8636-A277F98F7F36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da8051f59840be2c34ad8f26a24d049d38ebbaf5","datavalue":{"value":{"entity-type":"item","numeric-id":875665,"id":"Q875665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"425f8056b12e32cf9661173a6034225bd249fd15","datavalue":{"value":{"amount":"+0.86366606","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":"Q1185245$CC8CE21D-523F-421F-8F14-BA4BD204807F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afbce7358dccce50d1cb48acf62ef92dd948272c","datavalue":{"value":{"entity-type":"item","numeric-id":3652249,"id":"Q3652249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5087a963aaebfb95dfaae74f382bacff5cabb77","datavalue":{"value":{"amount":"+0.8620286","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":"Q1185245$99F56CA9-C65C-4DFF-B4AA-AD2A5B62022E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Perfect matching for regular graphs is \\(AC^ 0\\)-hard for the general matching problem","badges":[]}}}}}