{"entities":{"Q1916984":{"pageid":1927726,"ns":120,"title":"Item:Q1916984","lastrevid":71155809,"modified":"2026-04-13T19:51:20Z","type":"item","id":"Q1916984","labels":{"en":{"language":"en","value":"On the computational complexity of the solution of linear systems with moduli"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 902717"}},"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":"Q1916984$27FB223B-82E5-4B30-827A-918E586200B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d1344a62a2b8991fdf7628a40c4ca4833bc2cee4","datavalue":{"value":{"text":"On the computational complexity of the solution of linear systems with moduli","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1916984$F9362BDD-3B2E-4E97-A9D9-A78745988757","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a7a813ba93e51ed2cd31e7c9e65c203058785d49","datavalue":{"value":"0853.65040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916984$359AB0E1-2BFC-4FFB-91CB-770FAF3BB383","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5fe64179423bf6d74eac9b94a4509a48895da727","datavalue":{"value":"10.1007/BF02425914","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916984$05CECFB7-B6A0-45E5-9EF0-40263C9913F1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c7999e3e01d43838ac559f475f3b198149793512","datavalue":{"value":{"entity-type":"item","numeric-id":163536,"id":"Q163536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916984$50CC8F9C-9D9E-47E0-BB08-46D7615CE014","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de90f2fb62ce582a6d325b4c112b8bd95345e057","datavalue":{"value":{"time":"+1996-12-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":"Q1916984$26C24C8E-632E-46B0-A7C9-AF5C3787C893","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f18c2074a55bf87625ce59cee5456cb036bba58d","datavalue":{"value":"The paper deals with the computational complexity of the solution of equations of the form \\(Ax= D|x|+ \\delta\\). Note that the problem of computing vertices of the convex hull of the united solution set for a regular system of linear interval equations reduces to the above-mentioned system. The main problem is to find a polynomial-time algorithm that finds out whether the linear system with moduli is solvable for given matrices \\(A\\), \\(D\\) and vector \\(\\delta\\), and, in case of solvability, computes a solution to the system.   The first theorem proves that the problem of solvability of the linear system with moduli is NP-complete, if \\(A\\) is nonsingular, \\(A\\geq D\\geq 0\\), \\(\\delta\\geq 0\\) (the inequality ``\\(\\geq\\)'' is understood componentwise), and the number of solutions of the system is finite (possibly zero).   For an arbitrary system of \\(m\\) equations of \\(n\\) variables, Theorem 2 proves that there exists a polynomial-time algorithm of order \\(O((\\max\\{m, n\\})^3)\\) that finds out whether the system is solvable and computes a solution (in case of solvability) if \\(A\\) and \\(D\\) are rational matrices, \\(b\\) is a rational vector and \\(D\\geq 0\\), \\(\\text{rank}(D)= 1\\).   In a more general context, Theorem 3 states that, if \\(A\\), \\(D\\) are rational \\(m\\times n\\)-matrices, \\(b\\) is a rational \\(m\\)-vector, and \\(\\text{rank}(D)+ \\text{corank}(A)\\leq k\\), there is a polynomial-time algorithm of order \\(O((\\max\\{m, n\\})^{k+ 5})\\) that finds out whether the linear system with moduli is solvable, and computes a solution in case of solvability.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916984$E1A35EE6-06EA-4DB4-9688-6902988535A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916984$78958D41-7FB0-4D92-AC8F-997DACBF2135","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"355ea56a4f84d7973d94c70a8b1f92966ec83542","datavalue":{"value":"65Y20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916984$4E75B30C-66CB-470D-AF87-3794DB9BFC2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4d2aa49789d35e35613e1a84ce4788bfee1559e6","datavalue":{"value":"65G30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916984$D124CBFD-16E9-419D-8162-8C6F06D2868B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4835e95a65bcc71ca8fc4d3dca09212b35d07c58","datavalue":{"value":"902717","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916984$6AC4E9F6-2255-477A-B717-1593B3DA55E4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b44e0460de8b89a3695e54806f9b749b49a67a49","datavalue":{"value":"interval arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916984$67D02383-A059-4A9D-A244-DD5FA69DFEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d69bdf1ddb670c8f8af0584552d3d4ab167d21db","datavalue":{"value":"linear systems with moduli","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916984$207F8BC8-2E66-4003-9FFD-16A1F6F3D163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916984$9E5D70B7-32B7-4D5A-A22B-C25028DC3F5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bea72e7ec1ed4cc96ce6ad0106e7856140a67e39","datavalue":{"value":"linear interval equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916984$36EC0B0A-61A4-48D6-BD37-1CF4C4E57E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916984$B2D02E10-7477-4D7E-BA08-5F86E9EFCB3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1916984$21B8F0F9-19E5-40E7-8BD7-12979AC5EAF9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"acc293918b743e94faa2c614ca0fde8fd9ed697f","datavalue":{"value":{"entity-type":"item","numeric-id":1276133,"id":"Q1276133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916984$05ACF850-BE9B-47EA-8AEB-242379DF23DA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2f9e16b52bc8c390b9fea0fb31de1975133dd070","datavalue":{"value":{"entity-type":"item","numeric-id":455938,"id":"Q455938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916984$25CF5CAD-34F3-4E2E-880D-5C63820C8C6D","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":"Q1916984$140A0CDF-44BC-45D2-9A02-4319E6862F25","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f65538fd9946d6df0cd6c1f809a144da41b8a003","datavalue":{"value":{"entity-type":"item","numeric-id":3943082,"id":"Q3943082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916984$4A44CD11-1454-42BB-A228-08C4D871DBA8","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":"Q1916984$E1D50F0D-1220-4BB2-907F-A562CCB71673","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a36042ff23b85eb6865e76d1721ae397363eb5f7","datavalue":{"value":{"entity-type":"item","numeric-id":1899453,"id":"Q1899453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916984$BCBE9DA5-43AF-4565-A258-81F4FB9C7C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c001dd397cb92a2c48ebf13d0157bcc10fabd150","datavalue":{"value":{"entity-type":"item","numeric-id":3998722,"id":"Q3998722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916984$AE2668D1-2577-4D4C-AEC3-1903EA1166C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5873f62ebbbc187b4d2b36ab0625eee5e4138e75","datavalue":{"value":{"entity-type":"item","numeric-id":749156,"id":"Q749156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916984$6270E167-1568-4E5D-A245-5548A98FB54D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5de3f11e40dfd31c906840e2c437cd3691d8b249","datavalue":{"value":{"entity-type":"item","numeric-id":1916971,"id":"Q1916971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1916984$5EF536FE-89F4-4354-A227-29585C736771","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9639628d97a52e4c48ba4e8d7bbed9e4e032ff1","datavalue":{"value":"https://doi.org/10.1007/bf02425914","type":"string"},"datatype":"url"},"type":"statement","id":"Q1916984$CC393C7E-0163-4D3A-A136-591003C73469","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2092edc91b8e45644360fd17a62df5b64aaa1e43","datavalue":{"value":"W395333906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1916984$C61FD94C-55F6-42FF-AA4F-FB15768C2908","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bad03679e4813bfbb72c55cf87f9816ddef12c10","datavalue":{"value":{"entity-type":"item","numeric-id":1371175,"id":"Q1371175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef794f33da4e0668d09f14c11971abe7fb71c431","datavalue":{"value":{"amount":"+0.7917830944061279","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":"Q1916984$8003FD06-8010-4A41-8A4D-3574C85CBB39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea98d4afe84cdec1564aa6c0c5e91953a37bda50","datavalue":{"value":{"entity-type":"item","numeric-id":4446133,"id":"Q4446133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"693571e58ece04b9549235dc1e47016c63d654e2","datavalue":{"value":{"amount":"+0.7890675663948059","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":"Q1916984$7B657D63-06BF-478A-AC97-A67CEFD03660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00f4f553b6831402fd548a75ac377273729f75a7","datavalue":{"value":{"entity-type":"item","numeric-id":749156,"id":"Q749156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43399c30a16bdc26985835ea5b7f3aa32fbd47ef","datavalue":{"value":{"amount":"+0.7880117893218994","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":"Q1916984$DFB7285B-E556-475C-A727-27397808A3B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b3d2b74afb08354f4aa73efc4343ab51ce06aab4","datavalue":{"value":{"entity-type":"item","numeric-id":1362824,"id":"Q1362824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0bc990291d8fd8baa8108488cd1a267f20ccd049","datavalue":{"value":{"amount":"+0.7871648073196411","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":"Q1916984$2426F8C0-1870-41F6-A374-D45C6BD23783","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the computational complexity of the solution of linear systems with moduli","badges":[]}}}}}