{"entities":{"Q2577705":{"pageid":2588448,"ns":120,"title":"Item:Q2577705","lastrevid":44394819,"modified":"2025-11-22T15:32:55Z","type":"item","id":"Q2577705","labels":{"en":{"language":"en","value":"The equational theory of a nontrivial discriminator variety is co-NP-hard"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2243854"}},"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":"Q2577705$EF68E801-B459-4F3A-9E42-347382F276CD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e475c9be4cd268e27df4a368ae6c45c2b8ade422","datavalue":{"value":{"text":"The equational theory of a nontrivial discriminator variety is co-NP-hard","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2577705$B2B09CC2-1947-40B0-A8E0-6729342DB33F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5316b651f6b7f085353214fca8ab07f57100ccbe","datavalue":{"value":"1090.08007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577705$2F1E57F1-5D7E-4A12-BC20-69DEB706FE46","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b586c610b4126dc988da2f2411ac2d994312c53","datavalue":{"value":{"entity-type":"item","numeric-id":1883664,"id":"Q1883664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2577705$F263C493-D40A-4274-8812-11E2FC2762E9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8fa179c8715004e2374d4db0c3ce41b39558e95d","datavalue":{"value":{"entity-type":"item","numeric-id":178112,"id":"Q178112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2577705$A6953E95-EC51-43B1-AD56-EF810BB1B254","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a28896e5111b14a787c7b95f92ad273263b18f84","datavalue":{"value":{"time":"+2006-01-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":"Q2577705$86C55872-3B22-43BF-8954-7391ED5E5705","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e73be8377a917e84a4b2ee2c88591e06e34d0259","datavalue":{"value":"The main result in the paper is that the equational theory of any non-trivial discriminator variety is co-NP-hard. The proof is based on efficient reduction of distributive lattice equations to equations in the target discriminator variety, and on a result by \\textit{P. A. Bloniarz, H. B. Hunt III} and \\textit{D. J. Rosenkrantz} [``Algebraic structures with hard equivalence and minimization problems'', J. Assoc. Comput. Mach. 31, 879--904 (1984; Zbl 0628.68039)] proving that a certain set of lattice equations true in distributive lattices is co-NP-hard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2577705$AA91A5EF-FC9E-4EFB-86BF-A1531AB3D742","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4897136ea1c19614fe909b8db60c4ec176d94a78","datavalue":{"value":"08B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577705$849CB054-3C51-4B26-A594-41F94E7FBE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577705$13C53412-1161-4ACC-8F37-554D77043F49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577705$3A9FA867-42EE-4B14-9604-43D1A372EE87","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c3305f606e0840b38ad3f735fc4032ecace65fbe","datavalue":{"value":"2243854","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577705$32BB527A-C36C-4172-93BB-3581B9585BCA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d649755d7dec7fe8dd2722580b18ccd4bdd91b89","datavalue":{"value":"equational theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2577705$1648F3FD-C169-46B0-AB74-AAEBA3870A01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c6dd1981b07a4c4fb58bb4b18036831c634f9b9","datavalue":{"value":"discriminator variety","type":"string"},"datatype":"string"},"type":"statement","id":"Q2577705$9898D44B-8423-445B-870D-AF8D4AC7D633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2577705$0B20B497-5DE1-493F-9851-76A0404A8CEC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"57ad727308120c2d3a49a9849dfa008e9ce3bebc","datavalue":{"value":{"entity-type":"item","numeric-id":703859,"id":"Q703859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2577705$711CFA4F-7932-45FB-8975-A2C1F97D7547","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":"Q2577705$512492AD-AEE8-4990-BF5A-ACFEA26A474C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"921d78453941c507b1abf417e2982a0f0883001f","datavalue":{"value":"https://doi.org/10.1007/s00012-004-1894-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q2577705$278274BB-6E31-4BE3-BA24-F6DF564FA2B4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"80206b395700a8f9bbabdf9504dc2ccda082213b","datavalue":{"value":"W2070486197","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577705$A03E0634-02B1-4348-9222-7A9D635F9EA4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b4a5b5146d3422eb060f7d91fd734698641babf1","datavalue":{"value":"10.1007/S00012-004-1894-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577705$90FB6722-D36E-4BE9-92D3-B6C6386BBBC9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c7ba66abc3641448345c28ce869f50283aa2511","datavalue":{"value":{"entity-type":"item","numeric-id":4443193,"id":"Q4443193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e50d6d27faf69b9c30d732264090010da858ad2","datavalue":{"value":{"amount":"+0.8533111","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":"Q2577705$1C772523-038D-48CE-81C3-9E83E1299C05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25d4654d4ed738bb552002e89c188dd356aa271f","datavalue":{"value":{"entity-type":"item","numeric-id":4532124,"id":"Q4532124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04ffa942e2df3dcc30107b5f7e518e8980a05b58","datavalue":{"value":{"amount":"+0.8489026","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":"Q2577705$CC178C36-B87B-4835-8CC7-D5AD798C8836","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df0d05e3017f3ba17287c82928f9843aabc791e0","datavalue":{"value":{"entity-type":"item","numeric-id":3818292,"id":"Q3818292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8ebba8547432b3de0947e3a33bf900687cba928","datavalue":{"value":{"amount":"+0.84806836","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":"Q2577705$85405A54-0524-44AA-B835-67D2F28626C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7333661d771484a6a2751100fbe6f9bfd9a99b43","datavalue":{"value":{"entity-type":"item","numeric-id":4339470,"id":"Q4339470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fee88ff670e47504869176a19f44a2c00a135af7","datavalue":{"value":{"amount":"+0.8480345","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":"Q2577705$28D8D325-F4DB-463F-AE47-85452F69F8A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb814e2a6e4ef034067889b500dcf1a286888e1a","datavalue":{"value":{"entity-type":"item","numeric-id":3362257,"id":"Q3362257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b98d44d994834241a29106d823905840c17c5bd","datavalue":{"value":{"amount":"+0.84316814","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":"Q2577705$BC1146C4-2731-453A-84D2-E247CE83517B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"958f95053e0ea54e5d00afc588773a4728e9c9ad","datavalue":{"value":{"entity-type":"item","numeric-id":1280610,"id":"Q1280610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d91f911c4a13cc11ab426e451a6cc3b38186a4c9","datavalue":{"value":{"amount":"+0.84303653","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":"Q2577705$78194F83-7C36-43EA-BAB5-861908E5F6F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3a047f62cd8cc3bb0839f3a1d6f462a8e1df5b7","datavalue":{"value":{"entity-type":"item","numeric-id":3839876,"id":"Q3839876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac7201dc9afd9f0e464819d5cbc097b272fc63f0","datavalue":{"value":{"amount":"+0.84298015","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":"Q2577705$52C201B5-52B2-4AA5-91F5-71525E1186D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74846a1394461b77cf29929fd533cb4678823d29","datavalue":{"value":{"entity-type":"item","numeric-id":1404988,"id":"Q1404988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab62c1b0a0bc6ad0b6c0d23d11011c0c98e04139","datavalue":{"value":{"amount":"+0.8396859","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":"Q2577705$F2592BA4-8A87-4F45-974C-C1005E3970F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ffbdccf3dd983ded3f6348c0babc42f063ca3541","datavalue":{"value":{"entity-type":"item","numeric-id":4250066,"id":"Q4250066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0abd94f1e377f8be3c59fc9d7c2c279a5490efe7","datavalue":{"value":{"amount":"+0.8375945","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":"Q2577705$CBC0F62D-2FC6-42B6-8212-A2D685C9592D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2971afe90d6baacf7421061b1217d95f35616b83","datavalue":{"value":{"entity-type":"item","numeric-id":1200945,"id":"Q1200945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4bffa3411d34633bbe78e421de49374d92d96ac","datavalue":{"value":{"amount":"+0.8364039","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":"Q2577705$7E1E5851-0330-4832-ACFB-B3E056989225","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2577705","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2577705"}}}}}