{"entities":{"Q1300912":{"pageid":1311662,"ns":120,"title":"Item:Q1300912","lastrevid":70096893,"modified":"2026-04-13T12:25:08Z","type":"item","id":"Q1300912","labels":{"en":{"language":"en","value":"Resolving infeasibility in extremal algebras"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1331379"}},"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":"Q1300912$2998B0F5-9B3D-4817-841E-B45419BE0043","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4594fd350191e5174bcf58b6a130431dbee5312e","datavalue":{"value":{"text":"Resolving infeasibility in extremal algebras","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1300912$EEBE7E40-9C96-4CF0-A658-29F8012AC3E6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bc5046528ba26c93e204290d325c68872b11ed52","datavalue":{"value":"0932.15009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300912$C136F972-E01F-4903-BBDC-AE6168AFE8CA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7346d19980acf07958e0a8d6e3b42bbe3daf2507","datavalue":{"value":"10.1016/S0024-3795(98)10248-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300912$968ADCDA-C52E-46A6-9386-97BE32184D64","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"08d35f61923c3979b9f50899d051984c625fbe35","datavalue":{"value":{"entity-type":"item","numeric-id":847240,"id":"Q847240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300912$0AD83DFD-A966-4CC7-BE0B-93D6195A42B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d52c2c2b43c52164f3a6097277c563ef44e1032","datavalue":{"value":{"entity-type":"item","numeric-id":187116,"id":"Q187116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300912$FB179040-AC36-4E2B-A642-3D1782AE295E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300912$AAE84BA7-D7CE-43B8-9EF6-68DDBEED404C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b22f0234058b897ad308815846be004cdc7f94b2","datavalue":{"value":{"time":"+2000-03-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1300912$E22159FC-9B25-4E5A-B91C-8853B5682E60","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f4d1a619ba11a9d671f303357f562e199e929803","datavalue":{"value":"Two extremal algebras \\({\\mathcal B}=(B,\\oplus,\\otimes)\\) based on a linearly ordered set \\((B,\\leq)\\) are considered: in the maxmin algebra \\(\\oplus =\\max\\), \\(\\otimes=\\min\\), and in the maxgroup algebra \\(\\oplus=\\max\\) and \\(\\otimes\\) is a group operation. If a system \\(A\\otimes x=b\\) of linear equations over an extremal algebra is insolvable, then any subset of equations such that its omitting leads to a solvable subsystem is called a relieving set. The paper shows that the problem of finding the minimum cardinality relieving set is NP-complete in the maxmin algebra already for bivalent systems, while it is polynomially solvable for bivalent systems in maxgroup algebra and also NP-complete for trivalent systems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300912$CA58EB5C-A9FF-4D1A-8256-DF17343FD186","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f0b321fafd33da205994db3b946bd7cfe9a54983","datavalue":{"value":"15A30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300912$9831E070-0BA7-4F25-A63B-746CC6BAC581","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300912$A1D4F41F-E034-4565-8AA9-F02D95E8CBDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a45ae13c9fa089fa230a226367a6e2fc5f1bdfee","datavalue":{"value":"15A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300912$C5DBE3FD-6793-4471-BB7D-DBBDB5C8C6E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c34f634acb1b8725380773d01e99cfd67d95690","datavalue":{"value":"1331379","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300912$5E4C31FA-24F8-43D1-853F-B9B7C1E9B409","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85a42118390deea791e6fe02297813bb07428ae9","datavalue":{"value":"systems of linear equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300912$542DCCC6-5455-41FD-93D2-4BB61CA96435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300912$E1E47C91-B07C-4F80-8C45-022B465A436C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6a3b52566798d2758da978937b6513b591083317","datavalue":{"value":"extremal algebras","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300912$558012DB-B174-48A7-B32F-B5A080968939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39528afae56877bbc0505cf2d48c351bc7d2a5f4","datavalue":{"value":"maxmin algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300912$A2775737-EE16-41C4-8CA5-D4DB2F370F38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1899fe24aa4bb12ad18ca2edc13eec5127bc0d04","datavalue":{"value":"maxgroup algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300912$9C87856B-4B33-4490-8376-5C9C57C152B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f916969b622351664aba9b25e9aad00e259578fe","datavalue":{"value":"relieving set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1300912$849358EF-F9BE-4E2D-A4FD-07D5D673906C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8b1c63b64f12cbf9d72f82f0061a948cdc321576","datavalue":{"value":{"entity-type":"item","numeric-id":587860,"id":"Q587860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300912$3EF6FE57-08C8-4F95-BFED-53C764BF4003","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":"Q1300912$1ADA585D-1C71-4983-ADD9-2F0C9D6DD881","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f249580a521efbf8ec95a14e96ab42705350cf25","datavalue":{"value":{"entity-type":"item","numeric-id":4304869,"id":"Q4304869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300912$470E9F1B-F383-4B7D-90A0-2AB3CAD0AA49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f06f5550e9e145485a3b041a1f682842f5ed5b86","datavalue":{"value":{"entity-type":"item","numeric-id":3964346,"id":"Q3964346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300912$EB8C9E2D-DB78-4DCA-A8F3-80072CC6A304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0ffa901721ea92c0af23a9ecdcd8878ea9f103b","datavalue":{"value":{"entity-type":"item","numeric-id":1914494,"id":"Q1914494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300912$37F1E7E4-E0C1-42A4-99BA-32B98B4FB948","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":"Q1300912$04767EB6-82A1-45A2-8A07-2E146E1603E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"454674d7b03f55bfc989ffb3f1ea0d37460fa023","datavalue":{"value":{"entity-type":"item","numeric-id":2367035,"id":"Q2367035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1300912$752DFEFA-2F50-4CB7-93FB-222168351485","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ca146fddaa7ae350d8b1045185d6eaee2796770","datavalue":{"value":"https://doi.org/10.1016/s0024-3795(98)10248-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1300912$2BB0436E-1C18-4874-8257-BACE2DEDC278","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2a35b85cdaffc066c1f85cfc4c1794a89ebbd927","datavalue":{"value":"W2035068695","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1300912$C0548A25-489B-4143-BFFC-A53811AE0571","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e676aae0dd41ec002e87a5ec575afd2f636c047","datavalue":{"value":{"entity-type":"item","numeric-id":3337246,"id":"Q3337246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"013f5ddaa9a4be8e81b9942fe06236535d71e082","datavalue":{"value":{"amount":"+0.8207727074623108","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":"Q1300912$A3EB5018-4A8F-41D2-AACB-EA80FBB601AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30ebfcddeb2e78999194dbec0f415aeef7b8252a","datavalue":{"value":{"entity-type":"item","numeric-id":3585650,"id":"Q3585650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa0e6bf28ac402e1bd07d2e2b97bc9ac29f29f31","datavalue":{"value":{"amount":"+0.7532504200935364","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":"Q1300912$B577D619-209B-4017-B6FE-FF75369BC444","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"798fe9b18b411f004f464768ae44f9e3e2c2af98","datavalue":{"value":{"entity-type":"item","numeric-id":1175739,"id":"Q1175739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e75838f74e59a5340529159ded96bb5aad4f507","datavalue":{"value":{"amount":"+0.7479485273361206","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":"Q1300912$7F7F3586-090C-42EA-9360-C258917D70AC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Resolving infeasibility in extremal algebras","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Resolving_infeasibility_in_extremal_algebras"}}}}}