{"entities":{"Q1083370":{"pageid":1094122,"ns":120,"title":"Item:Q1083370","lastrevid":48992791,"modified":"2026-01-06T10:37:17Z","type":"item","id":"Q1083370","labels":{"en":{"language":"en","value":"The bounded subset sum problem is almost everywhere randomly decidable in O(n)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3976791"}},"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":"Q1083370$25FBFFBD-9F70-49CE-A423-AF96B9C13F65","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b958f69a2a82d9aa51561bed178425e7055eae57","datavalue":{"value":{"text":"The bounded subset sum problem is almost everywhere randomly decidable in O(n)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1083370$1576BC7F-4E4B-4A0E-93FC-CE8CBAC10712","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6e73c3f92cd02cfc4a14b30059eecfd2fd9ecec4","datavalue":{"value":"0604.90111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083370$0A7AA590-BB0E-4E4D-B707-AFB7CCAA592C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b2d9b3fd3183d69b8676b351ef63ca939d4fd608","datavalue":{"value":"10.1016/0020-0190(86)90123-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083370$FD2CA679-E1D7-474B-9E40-E8D27A5969F8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c3c432e1c092c4ddcb9972ecd00240d5e0e71387","datavalue":{"value":{"entity-type":"item","numeric-id":583233,"id":"Q583233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083370$9B85876A-4954-470E-BE08-5FBB579C1443","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a04ecc81832bff993b189ec55412cfe64658861b","datavalue":{"value":{"entity-type":"item","numeric-id":196797,"id":"Q196797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083370$8E6B88CD-F047-4710-8425-9F9A71F493E8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083370$71070039-1334-4DAC-B2F0-1E0610784FBC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1083370$DB64D49D-7E36-4853-BA90-D1A4F70471C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"611fce858d42149fd9940b3dff0fd89666144494","datavalue":{"value":"The subset sum problem is to decide, whether for given positive integers b, \\(a_ i\\), \\(1\\leq i\\leq n\\) the equation  \\[  (SS)\\quad b=\\max \\{\\sum a_ ix_ i| \\sum a_ ix_ i\\leq b,\\quad x_ i\\in \\{0,1\\},\\quad 1\\leq i\\leq n\\}  \\]  is true. Given a sequence \\(A=(A_ n)_{n\\in N}\\) of positive integers with \\(A_ n=o(n)\\) the A-bounded subset sum problem SS(A) is the set of all problem instances of type (SS) with \\(a_ i\\in \\{1,...,A_ n\\}\\) and \\(b\\in \\{1,...,nA_ n\\}\\). We show that for each A-bounded subset sum problem SS(A) an 0(n) randomized greedy algorithm finds the correct maximum with probability 1/2 for almost all problem instances. Hence the A-bounded subset sum problem is almost everywhere randomly decidable in 0(n).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083370$9C622984-A5BE-4835-B139-0870437BA5C7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083370$776F5312-B1EF-4E24-BFB3-8961EF9E5C13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083370$F8AD04A7-E86E-426F-BA7B-8408BF8E19F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6958ea3363ca9244e0da0201efd237a8410f9a0c","datavalue":{"value":"90C09","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083370$94A4080F-FE77-4D0C-AE71-333A1918E874","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f354ec8d65a6e890584d2e3929df617e76356483","datavalue":{"value":"3976791","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083370$C1FAD3A7-EB25-4065-8D3D-552737EB20EB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04c467c9e060fd0e7ddb66ee7667c46a0afc7c91","datavalue":{"value":"subset sum problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083370$B76CDCE0-A403-4965-BB91-F04C12EFDDCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8af2f6e9b31828713d0813a1be430f89086ad9b2","datavalue":{"value":"A-bounded subset sum problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083370$02380F07-8A85-48E0-AA95-F76C949D13AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"921138ab28aacc46efedf37375439dab0ff9090d","datavalue":{"value":"randomized greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1083370$6B5E01F9-DB6E-4C3B-9A8E-543426ACA106","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":"Q1083370$821C5CCA-647A-4E18-BAA5-C97696422F05","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"754243f4355ade6b8beed707cbfc64d0207c3367","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90123-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1083370$C99BB45F-A976-463B-9F6D-01652C1FFBFE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"dc8f2c40a5de280fc696aa74c79a4bcad9e66539","datavalue":{"value":"W2016574553","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1083370$BCABEEAD-EC2B-40E1-A197-04D29DD67459","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"22efb9ef6454847970e9f94c68cf86deea1d38a3","datavalue":{"value":{"entity-type":"item","numeric-id":1168896,"id":"Q1168896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083370$84B7E9D3-8D28-4D3D-996B-15ED61DA0E3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a308e30505dd380998190c7f81f45679fe7a55a5","datavalue":{"value":{"entity-type":"item","numeric-id":3292915,"id":"Q3292915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083370$9FBA8194-D154-468B-9419-07BBE81D8EF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"676c366572cc7b1b94822710eef840155b7f6490","datavalue":{"value":{"entity-type":"item","numeric-id":3887342,"id":"Q3887342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1083370$462DD2E7-13E1-4443-B483-DC4AE1F8E2C5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26606dfca992bde79eae362e63096290a8527ee6","datavalue":{"value":{"entity-type":"item","numeric-id":3148101,"id":"Q3148101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b13ef2993ea8fe1cc11998da92353aa9a3a21e10","datavalue":{"value":{"amount":"+0.8301686644554138","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":"Q1083370$B8B1E341-F367-4AFC-8576-7148D2AC6C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49d0fdf9f1f2253ee2871f992b30438f89dafaf7","datavalue":{"value":{"entity-type":"item","numeric-id":4313818,"id":"Q4313818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b13ef2993ea8fe1cc11998da92353aa9a3a21e10","datavalue":{"value":{"amount":"+0.8301686644554138","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":"Q1083370$94A725E8-0FE3-4897-9261-17E7FA9406DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae03c89a923a0eec0f96cb02b523251e3969c180","datavalue":{"value":{"entity-type":"item","numeric-id":4207577,"id":"Q4207577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7a0ac7f2732801b80971d763b5914c52b8439e7","datavalue":{"value":{"amount":"+0.8064318895339966","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":"Q1083370$B46710F9-CA0B-4D50-9F80-165FA56F5C17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4856bc456fcceb001c7373f6c1413959f629641","datavalue":{"value":{"entity-type":"item","numeric-id":1806779,"id":"Q1806779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f69e353784563906c18e9622751024db386f883","datavalue":{"value":{"amount":"+0.8009347319602966","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":"Q1083370$A13745ED-80E7-4FCF-9D0A-314EC3F1FC29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed6a02b3c54a3e8f9f4754ffec750de6a0be4533","datavalue":{"value":{"entity-type":"item","numeric-id":3722413,"id":"Q3722413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"555e0d861faec809cb9e71e425ca8acb40b13322","datavalue":{"value":{"amount":"+0.7998479604721069","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":"Q1083370$BF70D128-84EB-4D6D-BDD8-F5150D534B18","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1083370","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1083370"}}}}}