Well, Bitcoin mining by itself, without Lightning Network, is NP hard:

https://freedom-to-tinker.com/2014/10/27/bitcoin-mining-is-np-hard/The conclusion is that without a base fee, the system would work more efficiently.

It depends how you will construct your algorithm, but it is generally true. Transaction selection is NP hard (see: knapsack problem), however, if you sort them by "satoshi per byte" or something similar, you can simply select your transactions based on that, and reach quite good results in practice, even if your solution will not be always the best one.

For that reason, we have block weight, calculated with a single formula for witness and non-witness data. If we would have two different rules for 1 MB non-witness data, and 3 MB witness data, it would be worse, when it comes to checking, which transaction is more profitable to include. So, "satoshi per virtual byte" is easier to compute than "satoshi per byte + satoshi per witness byte".

My computer science question is how the fee function takes place and rises the time complexity by orders of magnitude if b is non-zero.

It depends, what is your goal. If you want to always pick the best existing solution, then yes, it is more complex. But if your goal is to have some approximation that works "good enough" in typical scenarios, then you can simplify it, and then your algorithm has lower complexity.

So, in Bitcoin, we use simplified solutions that you can see in typical implementations. But because of that "NP hardness", you can find some cases, where you will check some blocks, and notice that it was possible to pick some better set of transactions, and get higher fees. Or you can observe in LN that someone picked a route that was not the best one available at that time, and some node could route the same transaction cheaper than it did.

My guess is that if b is non-zero, the algorithm must take into account an extra parameter, that is the base_fee, and therefore increase the time complexity by orders of magnitude, because nodes need to consider not only the lowest fee rate when determining the cheapest path, but the best fee_rate : base_fee ratio.

Also, there is one more thing: imagine that "b" is always zero. Problem solved? Not really, because there is always an option to do the same transaction on-chain. And that constant cannot be eliminated, because you can always close your channel, and send your coins directly to the recipient, or even use those coins to open another channel, while closing the previous one.

Edit: some example for the knapsack problem (transaction selection problem), see:

https://en.wikipedia.org/wiki/Knapsack_problemYou have that Wikipedia example, and you can see, how it turns out, when you apply "satoshi per byte" as a "dollar per kilogram", to pack that 15kg knapsack:

$10 4 kg 2.50 $/kg 1

$2 1 kg 2.00 $/kg 2

$1 1 kg 1.00 $/kg 3

$2 2 kg 1.00 $/kg 4

$4 12 kg 0.33 $/kg (excluded)

And you can check all combinations to see the best solution (in practice brute forcing won't help, but for five "transactions" we can do that).

11111 $19 20kg (bad)

11011 $18 19kg (bad)

11101 $17 18kg (bad)

10111 $17 19kg (bad)

11001 $16 17kg (bad)

10011 $16 18kg (bad)

11110 $15 8kg (the best solution)

10101 $15 17kg (bad)

11010 $14 7kg

10001 $14 16kg (bad)

11100 $13 6kg

10110 $13 7kg

11000 $12 5kg

10010 $12 6kg

10100 $11 5kg

10000 $10 4kg

01111 $9 16kg (bad)

01011 $8 15kg

01101 $7 14kg

00111 $7 15kg

01001 $6 13kg

00011 $6 14kg

01110 $5 4kg

00101 $5 13kg

01010 $4 3kg

00001 $4 12kg

01100 $3 2kg

00110 $3 3kg

00010 $2 2kg

01000 $2 1kg

00100 $1 1kg

00000 $0 0kg

Then, you can see that we reached $15 items with 8kg weight. But, what would happen if there would be one more item worth $16 with 12 kg weight? It would have 1.33 $/kg, so it would be still included after the first two items (with 2.50 $/kg and 2.00 $/kg). And because those two items have 5 kg weight, adding 12 kg would exceed the 15 kg limit, so that item won't be picked.

So, as you can see, our transaction selection algorithm is "good enough". There is no guarantee that the total fee for a given block is the highest possible fee that a miner could take at a given time, having a given mempool. But in practice, our "good enough" solution is sufficient. The same for LN fees: finding the best route is NP hard. But we have simplified solutions that are sufficient.