{"entities":{"Q2332795":{"pageid":2343538,"ns":120,"title":"Item:Q2332795","lastrevid":57861036,"modified":"2026-04-02T20:31:05Z","type":"item","id":"Q2332795","labels":{"en":{"language":"en","value":"On polynomial-time solvable linear Diophantine problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7126248"}},"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":"Q2332795$4A916280-451C-42A9-B58A-935512AAC9E5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"785bd5a6e6f5dcf80fdf79ade18896ff3ac9fcfe","datavalue":{"value":{"text":"On polynomial-time solvable linear Diophantine problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2332795$8B76E174-719B-418D-9393-A2DE1625AE5C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0bbf70235abc7b49a49b84e9d66f04d9ad9fa954","datavalue":{"value":"1453.11042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$791BDF73-04E3-47E3-B7D3-8CB50D0B2160","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"96d61287f253fc18075a19b52e9e24b787406c3d","datavalue":{"value":{"entity-type":"item","numeric-id":266692,"id":"Q266692"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$E98920A2-79E8-428B-AEA3-B03EBEBC5E5B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bccc622163907dce47b152e149fdc3cca7991b48","datavalue":{"value":{"time":"+2019-11-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2332795$146118DF-B3AE-4F0D-91B7-DBF0EB27103B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1c4b934dcb04c197edc780bdb37c01004dbb8571","datavalue":{"value":"https://arxiv.org/abs/1903.06064","type":"string"},"datatype":"url"},"type":"statement","id":"Q2332795$ADF24AD4-1833-46EB-B12A-90F92C5DB467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"67cd103a85c3d35e8288910cfaf0bae667fb3fe6","datavalue":{"value":"http://orca.cf.ac.uk/124630/1/PolySubcone0107.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q2332795$D1C7614B-0871-40BA-B85A-FF3878C2C80D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7f41a10b4dfca41c55a943cf359e99fad6d07bc5","datavalue":{"value":"Let \\(A=(B|N)\\in \\mathbb Z^{m\\times n},m\\leq n\\) with a non-singular part \\(B\\in \\mathbb Z^{m\\times m}\\) and \\(b\\in\\mathbb Z^m\\). The author considers nonnegative integer solutions  of the system \\(Ax=b\\).  Denote by \\(\\ell_N\\) the Euclidean length of the longest column in the matrix \\(N\\). Let \\(\\mathcal C_B\\) be the cone generated by the columns of the matrix \\(B\\), denote by \\(\\mathcal C_B(t)\\) the affine cone of points in \\(\\mathcal C_B\\) at Euclidean  distance  \\(\\ge t\\) from the boundary of \\(\\mathcal C_B\\). Denote by \\(\\gcd(A)\\) the greatest common divisor of all \\(m\\times m\\) subdeterminants of \\(A\\). The author proves that if  \\[b\\in\\mathbb Z^m\\cap \\mathcal C_B\\left(\\ell_N \\left( \\frac{|\\det(B)|}{\\gcd(A)}-1\\right)\\right)\\] then there exists a polynomial-time algorithm which finds a nonnegative integer solution to the system \\(Ax=b\\) or determines that no such solution exists.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2332795$135A5418-0040-4287-B84D-10B925268CA7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f31233b552eca4a4ba62dfc962e070217fef4dcf","datavalue":{"value":"11D04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$D850FD65-64D0-4A02-AF73-11F9B805F7AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"221638ffca33675cdf942a4ef0bda6a6fb040b1e","datavalue":{"value":"11D07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$CEB088C6-8917-411D-AAB1-531B2FB3240A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"67c45964bb1554d8a802bf9a29e50db9b1c5a363","datavalue":{"value":"11Y50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$06E4F6F3-94A6-49FA-A93E-658123EDEF8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$87767819-341C-4EDA-A9FE-E398F56EBD19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"732c2501ca31f5ceeef797f80b885d9dde0d046f","datavalue":{"value":"11H06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$9174AC55-17D8-4E2B-8B0E-91FBE36538EE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"38bcfb9e2a895cda28f5d87c63554ce828e806ed","datavalue":{"value":"7126248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$4C70AD68-5694-45E9-A405-D11F000840A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c6d9df2caee0ceb34490bb01c31b1f6848f0972","datavalue":{"value":"multidimensional knapsack problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2332795$400D7904-79B1-4D01-B92F-867D6F43082A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a92166f5adeebffc8c81c6abb980ed495030be8","datavalue":{"value":"polynomial-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2332795$BD8E1332-8A5B-418C-A750-B8DF9035F8CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad7ec5b29f88d44ea616cc14fb6b76ef19467207","datavalue":{"value":"asymptotic integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2332795$31E74F09-6419-4B4D-A96C-FB1A4D9D1AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02fd21e2652775d60624658cb6c4e5cc261bd7f7","datavalue":{"value":"lattice points","type":"string"},"datatype":"string"},"type":"statement","id":"Q2332795$682C1B14-383A-42F2-A3AB-BC5302B9056A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a06bd306a47ea825067aa05768a86e5d250c8fa9","datavalue":{"value":"Frobenius numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q2332795$4A1FDC20-0E81-459C-85E6-212D82355AE9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"287ad700488d6c8cfc1e4b5b1febd8c09550d04d","datavalue":{"value":{"entity-type":"item","numeric-id":868898,"id":"Q868898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$65232EBA-3BE4-4EA8-BA7D-822BEC1560F3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6846a1cf39e2d8865eeb6207c5dffeda01e8cf68","datavalue":{"value":{"entity-type":"item","numeric-id":167120,"id":"Q167120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$0AF151F1-2FDD-40CD-8BE8-145F7F3B62E9","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":"Q2332795$75EAFB4B-ED9A-4E5D-8BCA-E222BBB38208","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d291d3b18611150b634b7d2ec1b901aa72eae1ec","datavalue":{"value":"W3100609971","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$762CB95A-8E89-46F1-A95A-08A5756A6D63","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"393cc41d1abfe63e2257a1636d09d1a0aca1ddab","datavalue":{"value":{"entity-type":"item","numeric-id":1928499,"id":"Q1928499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$FD6F290A-0B6B-4870-A495-6499976D6E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50cfad429314e1605f6ade5a2c59b3e9f12f443e","datavalue":{"value":{"entity-type":"item","numeric-id":1076512,"id":"Q1076512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$303558FC-8131-4684-BE61-68604AFDAB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39633f85c3f59cbfb465de8b6af9611f965045f2","datavalue":{"value":{"entity-type":"item","numeric-id":5840342,"id":"Q5840342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$64B9AAFE-6D7B-49B8-A9C2-A22F2AEE046D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea0d5c76be03aad1e7a3173f7f382d4e13fa566f","datavalue":{"value":{"entity-type":"item","numeric-id":5829099,"id":"Q5829099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$A8A6DDB6-21B8-4239-B692-AC2502F33F6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"852f72f594c5571ef288b693ca0bb8122a087a35","datavalue":{"value":{"entity-type":"item","numeric-id":2569821,"id":"Q2569821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$01939CDE-B120-4EFA-B1EB-19B632FD13FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da98d83333a4041ba9356afb37323237aa80e4fd","datavalue":{"value":{"entity-type":"item","numeric-id":3259120,"id":"Q3259120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$BE1267C8-890A-4F74-B5E2-A3F9B25B9754","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25a5404370bdb47bb25cef22a2d934aa56b98980","datavalue":{"value":{"entity-type":"item","numeric-id":2535821,"id":"Q2535821"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$AF98C0F8-DED1-4E8A-9FBB-70329FBB3F11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dcafb238e6ba98f691c336bb9a0d0dc6d0f213d","datavalue":{"value":{"entity-type":"item","numeric-id":3891677,"id":"Q3891677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$5745EC2D-82AE-4C1A-93F1-6AB7D6ACA6AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"975a2de2f83df1d7f594a7120f26625aaf3c77f7","datavalue":{"value":{"entity-type":"item","numeric-id":1189451,"id":"Q1189451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2332795$A8E58615-F3AF-4590-9463-A0A012E7EF27","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"0849e3961ce8bd8a1542102e246c8ebf679d5451","datavalue":{"value":"Q127086916","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$A0A219FF-FAB6-44F9-9A20-E303F490891C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4628eefbe11a13313a25be1efadeed71382c6811","datavalue":{"value":"10.2140/MOSCOW.2019.8.357","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2332795$43B04339-2E7C-4746-8B05-F76D106E3E36","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95bb572d4190a8e1f789ec94952d3ae380d21097","datavalue":{"value":{"entity-type":"item","numeric-id":3808157,"id":"Q3808157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da752c51287a5c702b970de6462f1507708b5de0","datavalue":{"value":{"amount":"+0.8181468844413757","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":"Q2332795$83539598-163F-4462-B728-6FCCBB6F6435","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12ab8354f3f966656f5f4a2480454e2a49f681ff","datavalue":{"value":{"entity-type":"item","numeric-id":4366594,"id":"Q4366594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a74309146e3445686b407061c18416491a0f813a","datavalue":{"value":{"amount":"+0.7897520065307617","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":"Q2332795$BD1CF362-02A5-462A-9F0A-F8C9D0B706CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c23e7cac5200937d89ee82059b9c0e51bdc367b","datavalue":{"value":{"entity-type":"item","numeric-id":2265948,"id":"Q2265948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da19c19d483255bb3f78b6de8fa82b78678564d2","datavalue":{"value":{"amount":"+0.7762395143508911","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":"Q2332795$3D40FA5B-CCB9-439B-AAC2-162D18A109E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bc8e93489f8d23cd459652cc579c3908cb5f24b","datavalue":{"value":{"entity-type":"item","numeric-id":1907269,"id":"Q1907269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9a2777c605b56d1425ea83aa550a2c873cd55c0","datavalue":{"value":{"amount":"+0.7753350138664246","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":"Q2332795$44318574-525E-40C3-AA1A-022CE2A23F98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f5beb0ea09b350bddf48e9db2d93971c832da295","datavalue":{"value":{"entity-type":"item","numeric-id":2760224,"id":"Q2760224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6792159a52ae171f665953287e79d5ee24245bd5","datavalue":{"value":{"amount":"+0.7742725014686584","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":"Q2332795$41AE1A0F-E683-487F-B601-1FF9DCD38392","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2332795","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2332795"}}}}}