{"entities":{"Q1770618":{"pageid":1781360,"ns":120,"title":"Item:Q1770618","lastrevid":48453307,"modified":"2026-01-04T20:51:43Z","type":"item","id":"Q1770618","labels":{"en":{"language":"en","value":"Checking quasi-identities in a finite semigroup may be computationally hard."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2153450"}},"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":"Q1770618$0B3A567A-EEBE-4051-88FA-8C080C682342","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f3fc4bf1e5e1b973c0aa5d6af5e0df32021566f8","datavalue":{"value":{"text":"Checking quasi-identities in a finite semigroup may be computationally hard.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1770618$2A0F8FAE-6CCC-4587-BC08-5C821AA98FF4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d7e64df77a49c7000efcd55f39d3f5c16511c27e","datavalue":{"value":"1076.20043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$E0BAED4D-AA1D-4CC5-A8A6-80ADDEE029DF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9836a36a6248613f2664814a87ea01a9c752cb6","datavalue":{"value":{"entity-type":"item","numeric-id":1729794,"id":"Q1729794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$0D8F167F-DF17-4AD0-B114-85E526E2A8D7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e34236ca73b92c6ee0bc17431d03c3537a7f0792","datavalue":{"value":{"entity-type":"item","numeric-id":195358,"id":"Q195358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$F3FD955C-9386-4178-928D-36EF5B2E2B9D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"86471ba8a812fc2d049bb06f25b4db84c76027a9","datavalue":{"value":{"time":"+2005-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1770618$E4F68FF0-5750-4AAE-8CB2-3671AFCDF8DC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f93846d16160d2f721fcc991af44d9f62c6efea","datavalue":{"value":"Many basic questions in algebra turn out to be (computationally) surprisingly difficult. For instance, it was shown by \\textit{C. Bergman} and \\textit{G. Slutzki} [SIAM J. Comput. 30, No. 2, 359-382 (2000; Zbl 0963.68077)] that the question of whether two finite algebras satisfy the same quasi-identities is NP-complete. This paper considers the question of whether a fixed finite algebra satisfies a given identity. This clearly belongs to co-NP, and in this paper a 10 element semigroup for which the question is co-NP complete is constructed. This is not the smallest possible such semigroup, but it is of interest because the checking of identities in it can be done in low polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770618$B16646D5-B3BF-4E1E-91B9-DF8F0AEE8C94","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f8414a3f118214cb0e61ac619ce4c188ec75d9e3","datavalue":{"value":{"entity-type":"item","numeric-id":587989,"id":"Q587989"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$EFD67246-D481-452A-9089-4EBEC23A7B97","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5fb4697c93e6483e0ffbb93428a373e0646b68d","datavalue":{"value":"20M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$2A19B90D-37AF-4284-A2D1-3D2FB1AD99E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$7FB2A76C-CBA8-43FF-9539-846A67006E37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$B2612674-84E2-497F-AB63-3D690BA4023F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$D203972B-6C4E-4969-801F-45F2B3CE01DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$C460452F-7243-4487-86D6-CE573B199E4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ba40962b9b1c6cc590e99c35b83dff6377a190fb","datavalue":{"value":"08C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$BA53BA92-13EB-4E09-8AE3-A1C5AD3FB573","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"46f2ddb9f000902c189e5bd6cd4b9f3d845feaaf","datavalue":{"value":"2153450","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$10D38AC8-0DF2-4B29-BA98-071FDA237EA3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f531b0e0a828fa7a37e8a4a90f6c1f6ca89420f2","datavalue":{"value":"finite semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770618$B0190F14-9353-4023-B5FD-D5ED3445D714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14d6a7c45b6fa152c1fa360245eff4f514052fa9","datavalue":{"value":"identities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770618$4FC020B9-94A0-439A-ACC4-4B94BF3D5AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb02c5c07c8f3975e80e6e8fc9b19e1b7b0e7e99","datavalue":{"value":"quasi-identities","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770618$A6D8EEF3-4BA7-4E5C-AA5B-74B7F9CBD9FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1770618$2BD4BFB2-5C9B-48E9-81A6-4414D9DD6B9B","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":"Q1770618$E6F98CFB-E1AA-451D-A0FA-E10FA3210A66","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f525aeac8deef054e9cc026974a128c6ae7d7791","datavalue":{"value":"https://doi.org/10.1007/s11225-005-0356-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1770618$3FBA8C88-D927-4DBC-B5BF-61D2824D3218","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"34aad5220def76cdef770f98b2bf5c4164452918","datavalue":{"value":"W2005496785","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$DE92F8CA-93B0-4426-843A-6EC0756BE233","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5549384f00be91893704f9c60426177f4bd66f7","datavalue":{"value":{"entity-type":"item","numeric-id":4507355,"id":"Q4507355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$2DA62A32-CDBD-43AF-9243-1FEBFB976338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5afbf744a209bae591f2001b963f84ed85dc6a7","datavalue":{"value":{"entity-type":"item","numeric-id":3848243,"id":"Q3848243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$491DE0DE-D139-45D0-9773-BB79D6B7C22B","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":"Q1770618$B8E5D8AF-ED26-4CAD-85D6-B1BA1FE273DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1163b75feea329c267b3957b69fa43261ded1771","datavalue":{"value":{"entity-type":"item","numeric-id":2655464,"id":"Q2655464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$E2A4C530-6108-4916-85B9-DED4DAD7C9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f88392e2d96e6b20b42940bf56c1735eaf4e5420","datavalue":{"value":{"entity-type":"item","numeric-id":3291034,"id":"Q3291034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$81CF28B5-A9F9-44E3-98E6-7511A29AE3BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$2B2A2F14-32DB-4726-84B8-3932BB16CC04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22b30fd147578354c576ab6eee82f0f88022fc5b","datavalue":{"value":{"entity-type":"item","numeric-id":5461667,"id":"Q5461667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1770618$297811A4-9469-4C89-A6BA-D7B5C82D04BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a349a5b55700e6bee025d0fd522431a00cc05d8","datavalue":{"value":"10.1007/S11225-005-0356-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1770618$0639C7E9-174E-42AD-B109-0D7861F8AC49","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05b91fb643c1dc82bd98074b9059de14389ddb39","datavalue":{"value":{"entity-type":"item","numeric-id":843593,"id":"Q843593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71c982c83753c9ba257bce1a7ca2833cc6d5ea9a","datavalue":{"value":{"amount":"+0.8521180748939514","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":"Q1770618$4DB43E82-3711-42BF-9F83-44D1872F75CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce2ff4b33526d8c2976a3461dc091366a15c6026","datavalue":{"value":{"entity-type":"item","numeric-id":4824699,"id":"Q4824699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5117984cba626b8cd875ba9a62855508440a26c4","datavalue":{"value":{"amount":"+0.8441352248191833","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":"Q1770618$3019A972-BF43-4B95-87BE-16F5D6BAF664","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3eacb3d47ba553bed6c80af1d4a1a95ad323b8c9","datavalue":{"value":{"entity-type":"item","numeric-id":4960463,"id":"Q4960463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98262728b250ae22a9180072197afb51fe794fb9","datavalue":{"value":{"amount":"+0.8191118240356445","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":"Q1770618$A0562FD9-0ABE-4246-AF07-D424A21DE40A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"168ee8b364fdd824e03167252e081edab0c86659","datavalue":{"value":{"entity-type":"item","numeric-id":2655464,"id":"Q2655464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12f461c2977e8cacc5060b98f429ced4b2d8e468","datavalue":{"value":{"amount":"+0.8017513155937195","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":"Q1770618$B1788A05-F42A-4BF2-8CA0-BB5ECE3A767C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8333b284db0ab9d10f45fb81823638a86a71c4cd","datavalue":{"value":{"entity-type":"item","numeric-id":444673,"id":"Q444673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"87d8e5f71dd208e48b1927105dbf60f6b0c07476","datavalue":{"value":{"amount":"+0.7771012783050537","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":"Q1770618$EE52CF10-F082-4ED3-9AAE-1B397209889A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1770618","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1770618"}}}}}