📅 Original date posted:2021-08-31 📝 Original message: On Thu, Aug 26, 2021 at 04:33:23PM +0200, René Pickhardt via Lightning-dev wrote: > As we thought it was obvious that the function is not linear we only explained > in the paper how the jump from f(0)=0 to f(1) = ppm+base_fee breaks convexity. (This would make more sense to me as "f(0)=0 but f(epsilon)->b as epsilon->0, so it's discontinuous") > "Do we really want users to solve an NP-hard problem when > they wish to find a cheap way of paying each other on the Lightning Network?"  FWIW, my answer to this is "sure, if that's the way it turns out". Another program which solves an NP-hard problem every time it runs is "apt-get install" -- you can simulate 3SAT using Depends: and Conflicts: relationships between packages. I worked on a related project in Debian back in the day that did a slightly more complicated variant of that problem, namely working out if updating a package in the distro would render other packages uninstallable (eg due to providing a different library version) -- as it turned out, that even actually managed to hit some of the "hard" NP cases every now and then. But it was never really that big a deal in practice: you just set an iteration limit and consider it to "fail" if things get too complicated, and if it fails too often, you re-analyse what's going on manually and add a new heuristic to cope with it. I don't see any reason to think you can't do roughly the same for lightning; at worst just consider yourself as routing on log(N) different networks: one that routes payments of up to 500msat at (b+0.5ppm), one that routes payments of up to 1sat at (b+ppm), one that routes payments of up to 2sat at (b+2ppm), one that routes payments of up to 4sat at (b+4ppm), etc. Try to choose a route for all the funds; if that fails, split it; repeat. In some case that will fail despite there being a possible successful multipath route, and in other cases it will choose a moderately higher fee path than necessary, but if you're talking a paying a 0.2% fee vs a 0.1% fee when the current state of the art is a 1% fee, that's fine. Cheers, aj