4 ms·
> There’s just one catch: No component of the vector describing the system’s state can ever drop below zero. Maybe, this is why we need debt in an economic sy
by jbandela1 3y ago
> There’s just one catch: No component of the vector describing the system’s state can ever drop below zero.
Maybe, this is why we need debt in an economic system, otherwise, certain transactions become intractable.
- strken 3y agoWould adding finite debt change anything? Borrowing capacity is still a floor, like zero, but it's a different floor for every actor. Maybe it'd make more problems solvable without reducing the complexity?
- not2b 3y agoIf you can go negative, it seems you've turned the problem into a Diophantine equation, the order of trades doesn't matter, you're just asking if we can get from the start state to the end state by using each possible trade an integer number of times.
- strken 3y agoIf you can go negative but there's a floor on how negative you can go, is it meaningfully different from not being allowed to drop below zero in terms of worst case complexity? The order of trades still matters in that case, right?
- not2b 3y agoYes, if there's no restriction the problem becomes a system of linear equations. If there's a limit, it's not linear and order matters.
- eru 3y agoAllowing negative numbers in this problems still leaves it NP-complete. That's much better, but still hardly tractable. Instead, allowing fractional numbers (with or without allowing negative numbers, doesn't matter), allows us to solve the problem in polynomial time. Debt is an interesting topic in economics (and sociology), but it's not the deciding factor here.