{"entities":{"Q1116696":{"pageid":1127445,"ns":120,"title":"Item:Q1116696","lastrevid":49254730,"modified":"2026-01-06T20:49:18Z","type":"item","id":"Q1116696","labels":{"en":{"language":"en","value":"Graph isomorphism is in the low hierarchy"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4090802"}},"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":"Q1116696$FC9EC5FC-F964-413D-A5F2-EF7D6F51A5B9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5a785e7bcc20162451252096e0988de8841ab97b","datavalue":{"value":{"text":"Graph isomorphism is in the low hierarchy","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116696$45228FCC-5025-48ED-A87A-3E31C4BA4188","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3d46f41c5553d15482939d65b23523ea0e9d0d57","datavalue":{"value":"0666.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116696$14BC063E-1904-4B86-8982-5F1530E4CC03","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f3fee9cf3aae8bac08b0f22b69c34b52664a4ad","datavalue":{"value":"10.1016/0022-0000(88)90010-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116696$C3EC6A21-2D9E-482C-A38F-5830BBCF70A1","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":"Q1116696$CD5DA2E8-8E0D-4350-836B-7B20A52510A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1116696$F81E0DF4-44A8-4640-BC10-704DD14F3106","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5e7c73cf8a0bf293a45f6d48a3f5c2e14b092a84","datavalue":{"value":"The paper deals with the membership of the well known `graph isomorphism' problem in some complexity classes. Two open problems are solved. First, it is shown that `graph isomorphism' is in the class \\(L^ p_ 2\\) that answers the question of the author [``A low and high hierarchy within NP'', ibid. 27, 14-28 (1983; Zbl 0515.68046)].    Under the assumption that the polynomial hiearchy does not collapse to \\(\\sum^ p_ 2\\) it is proved that `graph isomorphism' is not \\(\\gamma\\)- complete. This answers the open problem cf. \\textit{L. Adleman} and \\textit{K. Manders} [``Reducibility, randomness, and intractability'', Proc. ith ACM Symp. Theory Comput. 1977, 151-163 (1977)]. Hence `graph isomorphism' is not NP-complete unless the polynomial hierarchy collapses to some finite level.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116696$288761D5-98DE-461A-9948-884A5FBAE516","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116696$5B56DE32-B03B-47F7-95B7-382F76C63D6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"02303c61036060136df3f7b7e22c52163746633f","datavalue":{"value":"68Q99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116696$B3BF6B66-6B3D-41C2-B48A-FA6EDB0AC118","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d3ce590ddeb339ddcd3c94d58724a1cfca6cdb6c","datavalue":{"value":"4090802","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116696$3CFB7564-1A47-42E2-92CB-010408BF603B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8b9523b81abac7dcf2946305ecf06ced9bb8e7c3","datavalue":{"value":"structural complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116696$D0D3CD8D-8271-4DC2-A4E1-FFC05121C115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6d6f96eb45af643b8e3de12d655f5309b20b5eef","datavalue":{"value":"\\(\\gamma\\)-reducibility","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116696$34AAC33D-07C4-464A-8E5C-D6FDFA030FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116696$4F9EB234-D555-4F15-A51F-358D84C9C511","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1408da7db4c03e08918a50622f2fb337e63ab39f","datavalue":{"value":"complexity classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116696$B0D1D677-5F2A-4335-9B45-6CF1BF141E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"154ea0589dca3b50bef0f626c64f0e117c0eb521","datavalue":{"value":"polynomial hierarchy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116696$F9D496FF-059E-462E-BA43-8AA7262EB37B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"96373a06c4949477de69f6046a0c7f42f9cd2729","datavalue":{"value":"Q55878546","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116696$E9641F1C-8DCA-4EB7-94B1-FAA798CBC442","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"98e020d336f4040f2344877fb27890751f480383","datavalue":{"value":{"entity-type":"item","numeric-id":1052096,"id":"Q1052096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$85831047-E6B2-42D1-A18C-BED6230E7572","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"532bbaac3e370e50bd6ddecca89db5cad8ecea04","datavalue":{"value":{"entity-type":"item","numeric-id":1071506,"id":"Q1071506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$8B764526-3D75-4C78-80E0-8159AE4EFD38","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":"Q1116696$693A208C-BB48-4798-A822-8A71180D7042","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"25cc2f422cb77cc575a5631a2b440ed54bc36051","datavalue":{"value":"https://doi.org/10.1016/0022-0000(88)90010-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116696$EF147D0A-A645-462D-BF4D-F109ECBCB4D8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"36e57680eb52d9fc2f79963aeb855b7b6a8d7764","datavalue":{"value":"W2018099718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116696$00660515-DCEE-4415-B977-76972488E550","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"66eb6cafceb6ff937706546e940b98bf1f012a63","datavalue":{"value":{"entity-type":"item","numeric-id":1171880,"id":"Q1171880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$05BE3CB2-E334-4097-8475-AA4375C6EA6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54e3771f8171656e0aed45bf0777afe8aad7a3a9","datavalue":{"value":{"entity-type":"item","numeric-id":3902480,"id":"Q3902480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$4307FB39-6ED0-48E5-989B-02C84FD9C184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$F3E5386B-49BC-46CD-93D8-2B50E26F40BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac4b8e7cf4034c184fb2852754739a22a4e70036","datavalue":{"value":{"entity-type":"item","numeric-id":1108004,"id":"Q1108004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$972EE00A-77C1-4CFE-93F5-92C5C786EFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c847610ade77b047e3075d35766cbb1d381ec23","datavalue":{"value":{"entity-type":"item","numeric-id":1259907,"id":"Q1259907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$170AFF27-9A3C-4D27-AD13-A9ACF429D4D3","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":"Q1116696$7585D1B1-8EE9-4D52-B0F2-3C41ACBBBFA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eb24dff4005148539085ff5c885035cfccaed69","datavalue":{"value":{"entity-type":"item","numeric-id":4140967,"id":"Q4140967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$C3AAC026-6FC2-4D46-B2F4-D84C2E18FF40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b4feb58a2ab8f89621eb4513d36fed4a40d625b","datavalue":{"value":{"entity-type":"item","numeric-id":4365519,"id":"Q4365519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$F3C3AF2C-92D6-4D36-B11B-62DD18B7EF6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c435d235f5dd5d88317484b4ce4d5923395e2745","datavalue":{"value":{"entity-type":"item","numeric-id":1165581,"id":"Q1165581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$83196D11-383E-4480-B3CB-1324FECB843F","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":"Q1116696$A4B24AF9-BAF9-4261-BA98-87A71DDA39F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b543b24a2524e76130d5c1525baa40aa9abdeef","datavalue":{"value":{"entity-type":"item","numeric-id":3675520,"id":"Q3675520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$D7978C3F-AC46-44AB-9922-F427C110A006","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a2654c1ad3008ab65ddf962a999d4d8045dcdea","datavalue":{"value":{"entity-type":"item","numeric-id":4085242,"id":"Q4085242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$F8761CF3-DD2D-482F-99FC-69D23E03B783","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab289263ac80a8df854a0b026020c7e068e5240d","datavalue":{"value":{"entity-type":"item","numeric-id":1052094,"id":"Q1052094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$8D486AAB-B6A9-4647-97BE-4FEFE127F8AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe67cddb1d2e8d4582eb3ba360c56bb29576a54c","datavalue":{"value":{"entity-type":"item","numeric-id":3329452,"id":"Q3329452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$6A73F447-B90C-4FE5-8324-4A5D09E5EEEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a098647e2133258d563151bef051aaad7f30f8b","datavalue":{"value":{"entity-type":"item","numeric-id":1055405,"id":"Q1055405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$26E1DFDE-5A36-4FB3-943C-6047524F885A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1601fa351336c9b1b39e0d452ad761d903354e0","datavalue":{"value":{"entity-type":"item","numeric-id":1253098,"id":"Q1253098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$EC921C3E-C13F-468E-BFD3-D3ACE7A3F0CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a830cafef1f2c438cb7e2286bda476de992419e","datavalue":{"value":{"entity-type":"item","numeric-id":1052097,"id":"Q1052097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$D4313341-6F81-400A-BDC6-4F3EB66DFE37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63543c709dbc0dad9af888025f0c28158a4c2594","datavalue":{"value":{"entity-type":"item","numeric-id":802309,"id":"Q802309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$EF87AEEC-3889-481E-85D2-D9200FA04ECA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44ff2c269b97a88de0fe652e2add75347876b7e3","datavalue":{"value":{"entity-type":"item","numeric-id":1361890,"id":"Q1361890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$F89684CF-CBBC-4D1D-8680-C79E79EC4755","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4751cb99cfb27abec44f2378f8165a3a9a6376a","datavalue":{"value":{"entity-type":"item","numeric-id":1236109,"id":"Q1236109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$2F71FCCC-634B-4FC0-A218-FD1BEF29776C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c72aba4f754fb3aee58df56c633c6e4b5ddbcd5","datavalue":{"value":{"entity-type":"item","numeric-id":3718150,"id":"Q3718150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$D2C0B523-54B3-4811-940E-4ACD3D967574","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ef86d27229f88234625ab5cf631770a7bacc164","datavalue":{"value":{"entity-type":"item","numeric-id":794427,"id":"Q794427"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$0ED371AC-EF90-42A6-9197-11EFCE4A4130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3380ff6f4b5d07929c4c395a1faa8794b1c8021f","datavalue":{"value":{"entity-type":"item","numeric-id":3768891,"id":"Q3768891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116696$2C9B52B5-2FF0-46FB-9B97-67A8B8F4AAD0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc61b2a2b739bab892a76f5868ce10149148ec1e","datavalue":{"value":{"entity-type":"item","numeric-id":3758245,"id":"Q3758245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db68c981582fb09c78f016545850eeb23f8ac2a9","datavalue":{"value":{"amount":"+0.9323593378067015","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":"Q1116696$A8AC591E-122C-4AFC-B600-7699499F76E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33a98c2a01b13ea6a52c84171e3a748263dbf7f0","datavalue":{"value":{"entity-type":"item","numeric-id":1210331,"id":"Q1210331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98f5c847f7dce50b6e8657ec83c78b5f7f38b893","datavalue":{"value":{"amount":"+0.8471713662147522","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":"Q1116696$613E81EB-6A89-4BD9-9B4F-35F543250ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb32abbcce3cea45da895030e1655da934631270","datavalue":{"value":{"entity-type":"item","numeric-id":4501553,"id":"Q4501553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"149f6de44ede9a2db5e53c366bf38a9e4f735e70","datavalue":{"value":{"amount":"+0.8406918048858643","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":"Q1116696$F09A3D5C-9D4D-49F9-95E4-1A4262EF534E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3b855d94b4c9bb709a216369ce716af699e25e8","datavalue":{"value":{"entity-type":"item","numeric-id":5096798,"id":"Q5096798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d5e96c84770cb28df86a5ed1eddaa9d2ce04c7c","datavalue":{"value":{"amount":"+0.8366073369979858","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":"Q1116696$50102A5C-9473-4EC8-9A0B-3634B2955E57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"758531bb65ff554169199a649452d7e4270902f5","datavalue":{"value":{"entity-type":"item","numeric-id":4273947,"id":"Q4273947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72f0eabd6d190577cfd6c1fd1216a3be74828370","datavalue":{"value":{"amount":"+0.8225618004798889","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":"Q1116696$93DDC95A-FA72-43B9-9D16-9AAE1CD753B8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1116696","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1116696"}}}}}