{"entities":{"Q2353186":{"pageid":2363929,"ns":120,"title":"Item:Q2353186","lastrevid":74095221,"modified":"2026-04-14T18:20:51Z","type":"item","id":"Q2353186","labels":{"en":{"language":"en","value":"Complexity of tropical and MIN-plus linear prevarieties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6456704"}},"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":"Q2353186$24355A81-B5D6-4F9F-855B-797325BA1D47","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"65f062b7952dcda07e784ef3aa2f4a9523916046","datavalue":{"value":{"text":"Complexity of tropical and MIN-plus linear prevarieties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2353186$DDD2ED02-1B1E-4C6B-9953-813BAB01C14E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5920d1c593073ae41ee74b492dd9f0c45b15d5f8","datavalue":{"value":"1326.15039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2353186$20A1B80D-15FF-46EC-ACCB-0D7D817115F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b95d9a882aa98e5cd140caee9c20704a5e906352","datavalue":{"value":{"entity-type":"item","numeric-id":413294,"id":"Q413294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$FDC49268-BF69-47E0-9CD6-5CC6A3C4E2EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a4a79399764b502030de9c1fe7fb099f6c796d65","datavalue":{"value":{"entity-type":"item","numeric-id":1583885,"id":"Q1583885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$BBAD6E76-86EC-4C0C-B54F-EB91BA242ADC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$EB9E8994-87AF-47F4-9FC0-6FC29F4BB624","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"59031731cbce21fe47bb1ab36c5c33fe0f711557","datavalue":{"value":{"time":"+2015-07-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2353186$6621BA6B-7F14-498F-B564-414DF80D58AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"36f74900fde96442b66246bb9ea23df7829a0556","datavalue":{"value":"https://arxiv.org/abs/1204.4578","type":"string"},"datatype":"url"},"type":"statement","id":"Q2353186$A02E79BD-277E-4945-A99F-19DAD754FD50","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ead973b1188412ff8a61253de993de046c2727c3","datavalue":{"value":"This paper studies the complexity of computational problems for linear systems in tropical and min-plus algebras and, more generally, the interrelation between these two algebras. Both the solvability and the linear systems equivalence problems in tropical algebras are shown to be equivalent to mean pay off games, and likewise for the analogue problems in min-plus algebras. Moreover, computing the dimension of the solution space of a tropical linear system or of a min-plus linear system is found to be NP-complete. The techniques for the proofs are mostly combinatorial.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$C0AD5F03-C00B-44C9-B09D-2D90813DA264","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1043bbc04c5c09930e6ee78cf989508134d92d64","datavalue":{"value":{"entity-type":"item","numeric-id":209090,"id":"Q209090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$811B0B7C-D71A-4D21-A796-D0E78C70EF5C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5bc850efb57718f8497af55f559776989de771f","datavalue":{"value":"15A80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2353186$C815475A-8867-41EB-A46A-AA0CF0765F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2353186$72650F84-2571-45F9-9590-0692D0FECA50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2353186$3547FD89-F0B5-4E10-BB70-5C64852D9662","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b7fa018f821a592347c3771f573d93b95df9981c","datavalue":{"value":"6456704","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2353186$C60C8267-C538-4826-95D9-981D000416A9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cbf730405dc3736dc803a43d6ec111e3112d708b","datavalue":{"value":"tropical algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$C3869851-CEC5-466C-AF3A-3BDDEA6FF366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0dac9212253f0b758d8e97a6a1a46121294b32c4","datavalue":{"value":"min-plus algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$0F8C7D1F-B35D-4A83-B7AD-15DA1333BDC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53626d25964b55292ac367a150678c16fc7a7025","datavalue":{"value":"linear system","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$EB55FFBC-A65A-4970-A5C1-350AE22B5A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d08be6f7ad8da62ec6e1cfb385e8cc060cd14529","datavalue":{"value":"solvability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$05210355-E83A-4CA8-B62D-3CA7C5C02D75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$4052FAFA-CA5C-43EA-B071-B575F0883761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d718f237748f8d3d4de71f618e8640c7e3ff0bce","datavalue":{"value":"linear system equivalence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$034BB8F1-A4E3-428F-8D3C-2E2C4294806E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aea507f54b4e5ef4256848e7d76d00d8461fe97c","datavalue":{"value":"mean pay off game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$E156C622-12CE-4A36-B77E-303F5191B3B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2353186$5DFEFC72-DF87-497F-B099-037E3935D06B","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":"Q2353186$6804154D-834C-44FA-B00F-C19EA6A9E1F1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5ed19f660ef3bd5870672d9dd18697c0cdf1e9ee","datavalue":{"value":"W2077454887","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2353186$14DD1439-887D-491B-B95D-3D9514219BDF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ac901c708c183aa8e58846d883d9b07974caf86","datavalue":{"value":{"entity-type":"item","numeric-id":2882394,"id":"Q2882394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$42F6EF0D-6C65-48B1-927E-6C0B747099D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"440524371b6bf826fa2b4c34c7e9bd6c35c9a695","datavalue":{"value":{"entity-type":"item","numeric-id":550656,"id":"Q550656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$AE0B2C54-8162-40E0-9F7D-33DC8526B296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d8653d2e6f53b17cedec7b9470bcf88609d4f1f","datavalue":{"value":{"entity-type":"item","numeric-id":5320667,"id":"Q5320667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$28F9AC32-F099-4193-81C4-DD57EF6D7FE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f63fd6d1800e62801bb2750ad32883e25051fb08","datavalue":{"value":{"entity-type":"item","numeric-id":990130,"id":"Q990130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$38983DCB-B73F-4646-B6F7-7F42F78FCAEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"521baf9e9649c571d09269c7bc0a9e1db3eec213","datavalue":{"value":{"entity-type":"item","numeric-id":3565227,"id":"Q3565227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$065E8174-B4C0-4359-9CA7-2109D788A7E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4508ac8db7d59861c7fdd59debc4d0984c15f67e","datavalue":{"value":{"entity-type":"item","numeric-id":1947044,"id":"Q1947044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$807A0A58-03E5-43F1-B38F-0ED350CA7FF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77fd56549136e337ad67107d48f2d866cfa772f2","datavalue":{"value":{"entity-type":"item","numeric-id":5290261,"id":"Q5290261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$456F1EDC-D0B2-4DCB-BD10-7DD79AF4DAE0","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":"Q2353186$03347EB3-ECAF-421D-A438-2447952CD8D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45ed447b7a919af83f0eadbabf5e631ecba52874","datavalue":{"value":{"entity-type":"item","numeric-id":2353186,"id":"Q2353186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$8742D551-6F92-442F-ACAD-DAFE5FD0FD8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"867a0724489ca6fd247c1d1397942e885e8bd5b5","datavalue":{"value":{"entity-type":"item","numeric-id":5898662,"id":"Q5898662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$8CE07388-8E3C-4EED-B7B8-2773205EEEB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d077ffe176e3a4058003a91c6349596baccd7da1","datavalue":{"value":{"entity-type":"item","numeric-id":5469209,"id":"Q5469209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$AACAE5E1-06EC-472D-A9B7-BAD317035769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"defab6eee23606f800a77f17d44e7fce0e25cd0a","datavalue":{"value":{"entity-type":"item","numeric-id":4412830,"id":"Q4412830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$9CF54B58-A777-4443-83EB-F39E54549F5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0997a238dab29397916c0a0de1da484cff6e849","datavalue":{"value":{"entity-type":"item","numeric-id":4651470,"id":"Q4651470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$9BD31006-6710-4749-82FA-E2C65DCB766A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a727762852bffafeed9118db8d661195c11b43b9","datavalue":{"value":{"entity-type":"item","numeric-id":5702484,"id":"Q5702484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$9EC07917-2779-49BA-8A9D-DD93A6C1FF3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"322a9017aa840f546f25e07f3021d250f9dba4d8","datavalue":{"value":{"entity-type":"item","numeric-id":4781203,"id":"Q4781203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$05CEBA22-B27C-4C76-95A0-FB8E882922F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cb2c660be11a317b29d915aac89f7fc5226f696","datavalue":{"value":{"entity-type":"item","numeric-id":2457404,"id":"Q2457404"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2353186$3ED34407-980B-4AE4-AB4F-83109A205471","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6fd35567fdc74f0654546b0ccc4731a3740ba4a4","datavalue":{"value":"10.1007/S00037-013-0077-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2353186$F20B8BAA-7C70-4418-AA6F-D4DEE945FEAE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39e1b516dc0fa8290c2c6c27fffc5a9733b3edf2","datavalue":{"value":{"entity-type":"item","numeric-id":5369334,"id":"Q5369334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"763e22f3e4311f45dd5fe73f8ffdee6c2bbdfde5","datavalue":{"value":{"amount":"+0.8246746063232422","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":"Q2353186$C72F685D-84A2-43BB-9629-E944559BE44A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"792d324ebcf6e89a3386d50076c0e15c8ec9f38b","datavalue":{"value":{"entity-type":"item","numeric-id":2942936,"id":"Q2942936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cf4b29b1a5cd338e1926297e0da9b21ce6cb890","datavalue":{"value":{"amount":"+0.7857476472854614","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":"Q2353186$7A182843-97D7-462E-B2AE-FC83AB6C6C25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afd11316cb33ef8244d4fae9fd0b5a36ce2b044e","datavalue":{"value":{"entity-type":"item","numeric-id":2188843,"id":"Q2188843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"844fe937febae684b2e992a030a814fc08090a37","datavalue":{"value":{"amount":"+0.7852329611778259","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":"Q2353186$DA849ABB-EDE0-40A1-887D-0D37CD750856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f569b3c6e59a3cd7ead18e487d33cbf92a4316a3","datavalue":{"value":{"entity-type":"item","numeric-id":2882394,"id":"Q2882394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93c34c2776ec4661d4fbb9bf422c47dbd8d3dea7","datavalue":{"value":{"amount":"+0.7809174656867981","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":"Q2353186$2E4094BE-FEB7-44B4-A802-A89D57E91747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5e778101ddc02141f625ad99061a25873e12601","datavalue":{"value":{"entity-type":"item","numeric-id":2032307,"id":"Q2032307"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75cf88a8e6076626c48be0541e0931c13cb4b37d","datavalue":{"value":{"amount":"+0.7791195511817932","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":"Q2353186$706778B3-97CC-4F45-B36E-F1E3213AFED2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Complexity of tropical and MIN-plus linear prevarieties","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Complexity_of_tropical_and_MIN-plus_linear_prevarieties"}}}}}