NP困難とライトニングネットワークの手数料関数が及ぼす計算量

以下のスレッドを読んでの備忘録。

https://bitcointalk.org/index.php?topic=5437244.0

ライトニングネットワーク（LN）での経路選択は、巡回セールスマン問題としても知られている。巡回セールスマン問題で、すべての都市を通る経路の計算をする場合、計算量はΘ(N!)なので指数関数時間となる。

そこで、LNではダイクストラ法※などの動的計画法を用いて比較的効率的に最適な経路を選択するような実装がされている。しかし、最適な経路選択するうえでも以下のような問題が指摘されている。（※計算量はΘ(E + V*log(V)) 、Eはチャネル数、Vはノード数）

LNでは手数料の合計値が最小であるような経路選択が望ましい。手数料関数をf(x) = rx + b、rは手数料率（fee rate）、bは基本手数料（base fee）とする。この関数は、b = 0でない限り、線形代数的には線形ではない。線形性を有するには、 f(x+y)=a(x+y)+b=ax+ay+b=(ax+b)+(ay+b)=f(x)+f(y) を満たす必要があるが、手数料関数においてはb = 0 の場合のみである。線形性を持つ問題は数学的に解きやすいが、手数料関数にはこの性質がないため（基本手数料であるbをなくせばよい）、経路選択という最適化問題を解くことが難しくなる。

スレッド内で質問されていた手数料関数がどのくらい計算量に影響を与えるかの具体的な数値の回答はなかった。もしかしたらこちらの論文に記載されているのかもしれないがしっかりと読めていない。

余談
上記の手数料関数で、f(0) = 0 だが δ→ 0 なので f(δ) → bであり、これは x = 0 において連続で、そこで 0 から b へとジャンプする不連続性を持つ。これは凸性を失うので（凸性も最適化問題を解くのに重要な性質）、手数料関数の最適解を解くのが難しいと言われる。この 0 から b へジャンプするというのもイマイチ理解できていない…