7 ms·

An easy-sounding problem yields numbers too big for our universe

79 points by abhi9u 3y ago

mjevans 3y ago
My eyes glazed over midway through the article. I'd like them to not try explaining the problem but just out and say what the problem is, then try to explain the details so that I can pick at the pieces I don't get well enough. I THINK the issue is probably something along the line of: Every new type of thing adds a new dimension / fold / layer, and operations that transfer between layers can occur in any cycle. This leads to an exponentially complex area of valid states in a high-dimensional setting, likely with upper and lower bounds as the shape exists across dimensions. This sounds possibly intractable to define the more potential actions / actors are involved. Thus it is very difficult to reach or process an equation that defines said shape and thus validates if a co-ordinate within the system space exists on or within the surface of the valid states of the system.
- anonymouskimmer 3y ago
  I often have this issue with Quanta articles too, for some reason. And agree that a change in article organization might solve it.
  - Jeff_Brown 3y ago
    Right. I'd classify this article under `wow/` and not `aha/`.
- hwayne 3y ago
  If you're up for the challenge, the original paper proving ACK-completeness is here: https://arxiv.org/pdf/2104.13866.pdf https://arxiv.org/pdf/2104.13866.pdf
deadbabe 3y ago
A humble request: someone please write the problem out in its entirety. Thank you!!
- itishappy 3y ago
  > Suppose, for instance, that a kindergartner named Alice has two apples, but she prefers oranges. Fortunately, her classmates have developed a healthy fruit-trading system with strictly enforced exchange rates: Give up an apple, say, and you can get a banana. Can Alice execute a series of trades, by picking up and offloading bananas or cantaloupes, that gets her to her favorite fruit?
  - not2b 3y ago
    I think the GP was asking for more detail than that. We have a dimension n. We have a set of vectors, each with n integer components. In the fruit-trading problem these represent legal trades. We have a starting state, with n non-negative integers. To do a "trade" we select one of the vectors in the set and add it component by component. The result must be non-negative (each component). The question to answer is whether, from a given starting state, we can reach a given ending state. The result here is that solving this reachability problem can be hellishly complex.
- Nick87633 3y ago
  I did a bit of noodling on the wikipedia page for VASS... Maybe I can make an example with software context... and this is probably wrong in some way so take with a grain of salt! Take as an example a directed graph representing a state transition diagram of a state machine. The machine has some integers (we can call it memory) as its internal state as well as having its graph location. Each state transition moving from one node of the graph on its available outbound transitions has an associated effect on the integers in memory (addition or subtraction particular to each state transition). The VASS reachability problem: Given a state (memory values and location in the state graph), can you reach some other arbitrarily chosen state by navigating the transition graph, while also not allowing the integers in memory to become negative. What is the guaranteed maximum time complexity for deciding whether any arbitrarily chosen final state is reachable? VAS - the same problem but without the directed graph restricting access to vectors. I think this one can be intuited as a "vector walk" that must stay in the positive quadrant going from a given start location to a given end location and a list of available vectors that can be used to move around in the space. Edit: if someone more knowledgeable is reading, please let me know anything incorrect and I will delete or edit.
tromp 3y ago
> It’s physically impossible to write down all the digits of 2^^6 — a liability of living in such a small universe. What a coincidence! Just today I learned that someone found a 49 bit program whose output far exceeds Graham's number [1], and the number 2^^6 features very prominently in it. [1] https://codegolf.stackexchange.com/questions/6430/shortest-terminating-program-whose-output-size-exceeds-grahams-number/263884#263884 https://codegolf.stackexchange.com/questions/6430/shortest-t...
- deleted 3y ago
  [deleted]
pixl97 3y ago
Not exactly related, but still a fun article that covers tetration and how stupidly big simple systems can get. https://waitbutwhy.com/2014/11/1000000-grahams-number.html https://waitbutwhy.com/2014/11/1000000-grahams-number.html
lowbloodsugar 3y ago
So for those not familiar, 2^^4 is not ((2^2)^2)^2, it's 2^(2^(2^2)). So 2^5 is 2^65536. 2^6 is 2^(2^65536).
- ninju 3y ago
  corrections on the last sentence (I believe you forgot the extra ^s) 2^^5 is 2^65536. 2^^6 is 2^(2^65536).
  - lowbloodsugar 3y ago
    Doh! I did yes! Thanks!
Jeff_Brown 3y ago
Why is it so hard?
- eru 3y ago
  Combinatorics and integers are hard. If you allowed fractional exchanges, this problem becomes easily solvable in polynomial time.
- beders 3y ago
  I think the issue is that the set of "operations" you can do on the start vector is limited.
renewiltord 3y ago
Interesting result. That's far faster growing than I would have anticipated since it seems intuitively like taking steps in a n-dimensional space which does grow fast, just not in a tetrative sense.
bgribble 3y ago
So given a start state and a library of valid transitions, it's easy to create a (target, path, destination) tuple that's valid (if you don't care what the destination is). It's easy to check if a (target, path, destination) tuple is valid. It's just really hard to find the path given just the target and the destination. This sounds like it has properties in common with "multiply two very large primes to create a very large composite number". Could any of this math be used as the basis for a cryptosystem?
- duleee 3y ago
  Reminds me of this: https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography
  - x3n0ph3n3 3y ago
    That's immediately what I thought of and was perplexed why the word "lattice" was nowhere in that article.
- WorldMaker 3y ago
  That description sounds similar to me of Elliptic Curve cryptography, as well. Pathfinding/curvefitting between two or more points in a curve without knowing other specifics of the curve.
- SuchAnonMuchWow 3y ago
  Depending on your library of valid transition, it could be really easy to find a path. That's the issue: there are libraries of paths where finding a path is really hard, but libraries where finding a path is easy. Say in another way, we know only the worst case complexity, not the complexity of a test case taken randomly. Some latices-based cryptosystems have such properties: there are theorems showing that if there is an algorithm good at solving random cases, than you can derive from it an algorithm good at solving any cases, including the worst ones. So for those problems, the worst case complexity is the same than the "average/random case" complexity.
hwayne 3y ago
This problem has a deep connection to formal methods: one of the first formal models of concurrent computing was Petri nets, which are equivalent to VASes. Petri nets are very limited in what they can model, and so finding reachability even those tiny, limited programs is HACK-complete! What I love so much about this is that it's really hard to find intuitive examples of TOWER-complete or even 2-EXPTIME-complete programs, but this one is so much harder than all of them but can easily be explained to a fifth-grader. Next goal is to find an intuitive HYPERACK problem...
7373737373 3y ago
The concept of reachability is pretty interesting in general as well. "Can a spaceship with a certain delta-v reach another planet within an n-body system? (And if so, what is the fastest-to target/most resource preserving acceleration schedule?)" - apparently necessitates brute force, practically not computable on long time scales due to the chaos inherent in n-body systems (https://space.stackexchange.com/questions/64392/escaping-earth-how-could-one-attempt-to-find-the-best-solution-to-this-traject https://space.stackexchange.com/questions/64392/escaping-ear..., https://en.wikipedia.org/wiki/N-body_problem https://en.wikipedia.org/wiki/N-body_problem) "Can a math proof be reached (within a certain number of proof steps) from the axioms?" - equivalent to the halting problem in most practical systems (https://math.stackexchange.com/questions/3477810/estimating-meta-mathematical-properties-of-conjectures https://math.stackexchange.com/questions/3477810/estimating-...) "Can a demoscene program with a very limited program size visualize (or codegolf program output) something specific?" - asking for nontrivial properties like this usually requires actually running each program, and there are unfathomably many short programs (https://www.dwitter.net/ https://www.dwitter.net/ is a good example of this) "In cookie-clicker games, is it possible to go above a certain score within a certain number of game ticks using some sequence of actions?" - in all but the simplest and shortest games (like https://qewasd.com https://qewasd.com), this is at least not efficiently (optimally) solvable using MILP and the like, as the number of possible action sequences increases exponentially And yet, despite these being really hard (or in the general case, impossible) problems, humans use some heuristics to achieve progress
- westurner 3y ago
  Quantum Discord: https://en.wikipedia.org/wiki/Quantum_discord https://en.wikipedia.org/wiki/Quantum_discord Quantum nonlocality: https://en.wikipedia.org/wiki/Quantum_nonlocality https://en.wikipedia.org/wiki/Quantum_nonlocality Butterfly effect -> Quantum chaos: https://en.wikipedia.org/wiki/Quantum_chaos https://en.wikipedia.org/wiki/Quantum_chaos -> Perturbation theory: https://en.wikipedia.org/wiki/Perturbation_theory_(quantum_mechanics) https://en.wikipedia.org/wiki/Perturbation_theory_(quantum_m... But then entropy in fluids, Satisfiability > Model Theory: https://en.wikipedia.org/wiki/Satisfiability https://en.wikipedia.org/wiki/Satisfiability Goal programming: https://en.wikipedia.org/wiki/Goal_programming https://en.wikipedia.org/wiki/Goal_programming And, ultimately, Self play (AlphaZero, ) https://en.wikipedia.org/wiki/Self-play https://en.wikipedia.org/wiki/Self-play "Q: LLM and/or an RL agent trained on [Lean mathlib] and tests" https://github.com/leanprover-community/mathlib/issues/17919 https://github.com/leanprover-community/mathlib/issues/17919
swader999 3y ago
I often wonder if the math for evolution is a similar problem. There's only a limited string of code that will survive and thrive. There's a set of evolutionary milestones or versions that need to happen to get where we are. There's a fixed amount of time on earth or perhaps the universe. Is there really enough time for all those dice roles?
- eru 3y ago
  I'm not sure what you are aiming at? Most of the competition in life comes from other living things. So any organism's failure to survive and thrive is often because some other organism is stealing their lunch money. But the 'lunch money' (eg a spot in the sunlight) doesn't disappear. > There's a fixed amount of time on earth or perhaps the universe. For the universe: it looks like the universe will expand forever, and more and more of it will recede behind the cosmological event horizon (because places that are far enough away will recede faster from us than the speed of light). The amount of usable energy within the spacetime we can reach is most likely finite. (Where 'usable energy' include considerations of entropy.) Time might be unlimited in an endlessly expanding universe, but usable energy ain't. But here's the savings grace: as far as we can tell, the physical lower limit of usable energy required for doing computations is proportional to the prevailing temperature. And expansion decreases the temperature of space, or rather its background radiation. So if you have 1J of energy left in your civilisation, you can expand half of it now to do some unit of computation. Then you wait until the temperature of your corner of the universe has dropped in half, and you expend another half of your remaining energy (1/4 J), to do another unit of computation. You can in principle keep doing this indefinitely, and get an infinite amount of computation. You can use that computation to power eg a simulation of life. --- Of course, this assumes you have found materials or mechanisms to run your computation on that can persist for arbitrary amounts of time in stasis without decay or using energy. The lower limit of energy usage for computation also only applies for irreversible computation. Reversible computation can be had for free, in principle. With long enough timescales, Boltzmann brains or even Boltzmann planets or Boltzmann galaxies also become a consideration.
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 ago
  Would 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 ago
    If 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 ago
      If 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 ago
        Yes, 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 ago
  Allowing 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.
Rapzid 3y ago
Kind of a bad way of explaining it to people familiar with reducing problems to reachability so they can be solved efficiently lol.
dclowd9901 3y ago
> “That’s a very natural restriction for a model of reality,” said Wojciech Czerwiński, a computer scientist at the University of Warsaw. “You cannot have a negative number of apples.” I realize this is probably outside the interest bounds of the problem space, but I could indeed have negative apples if I owe someone apples I don’t have.
- dragonwriter 3y ago
  No, then you would have however many apples you actually have, as well as an obligation to provide someone more apples than you have. Having an obligation to provide a thing is not actually the same thing as having negative one of the thing, even though it may occasionally be useful for some purposes to treat them as the same thing. (This is somewhat less true with money and things that work like it, since those things are essentially themselves already a social exoectation of future goods and services from other people, so the difference between an obligation of money and actual money is somewhat less than with other things.)

79 points by abhi9u 3y ago

My eyes glazed over midway through the article. I'd like them to not try explaining the problem but just out and say what the problem is, then try to explain the details so that I can pick at the pieces I don't get well enough. I THINK the issue is probably something along the line of: Every new type of thing adds a new dimension / fold / layer, and operations that transfer between layers can occur in any cycle. This leads to an exponentially complex area of valid states in a high-dimensional setting, likely with upper and lower bounds as the shape exists across dimensions. This sounds possibly intractable to define the more potential actions / actors are involved. Thus it is very difficult to reach or process an equation that defines said shape and thus validates if a co-ordinate within the system space exists on or within the surface of the valid states of the system.

anonymouskimmer 3y ago
I often have this issue with Quanta articles too, for some reason. And agree that a change in article organization might solve it.
- Jeff_Brown 3y ago
  Right. I'd classify this article under `wow/` and not `aha/`.
hwayne 3y ago
If you're up for the challenge, the original paper proving ACK-completeness is here: https://arxiv.org/pdf/2104.13866.pdf https://arxiv.org/pdf/2104.13866.pdf

deadbabe 3y ago

A humble request: someone please write the problem out in its entirety. Thank you!!

itishappy 3y ago
> Suppose, for instance, that a kindergartner named Alice has two apples, but she prefers oranges. Fortunately, her classmates have developed a healthy fruit-trading system with strictly enforced exchange rates: Give up an apple, say, and you can get a banana. Can Alice execute a series of trades, by picking up and offloading bananas or cantaloupes, that gets her to her favorite fruit?
- not2b 3y ago
  I think the GP was asking for more detail than that. We have a dimension n. We have a set of vectors, each with n integer components. In the fruit-trading problem these represent legal trades. We have a starting state, with n non-negative integers. To do a "trade" we select one of the vectors in the set and add it component by component. The result must be non-negative (each component). The question to answer is whether, from a given starting state, we can reach a given ending state. The result here is that solving this reachability problem can be hellishly complex.
Nick87633 3y ago
I did a bit of noodling on the wikipedia page for VASS... Maybe I can make an example with software context... and this is probably wrong in some way so take with a grain of salt! Take as an example a directed graph representing a state transition diagram of a state machine. The machine has some integers (we can call it memory) as its internal state as well as having its graph location. Each state transition moving from one node of the graph on its available outbound transitions has an associated effect on the integers in memory (addition or subtraction particular to each state transition). The VASS reachability problem: Given a state (memory values and location in the state graph), can you reach some other arbitrarily chosen state by navigating the transition graph, while also not allowing the integers in memory to become negative. What is the guaranteed maximum time complexity for deciding whether any arbitrarily chosen final state is reachable? VAS - the same problem but without the directed graph restricting access to vectors. I think this one can be intuited as a "vector walk" that must stay in the positive quadrant going from a given start location to a given end location and a list of available vectors that can be used to move around in the space. Edit: if someone more knowledgeable is reading, please let me know anything incorrect and I will delete or edit.

tromp 3y ago

> It’s physically impossible to write down all the digits of 2^^6 — a liability of living in such a small universe. What a coincidence! Just today I learned that someone found a 49 bit program whose output far exceeds Graham's number [1], and the number 2^^6 features very prominently in it. [1] https://codegolf.stackexchange.com/questions/6430/shortest-terminating-program-whose-output-size-exceeds-grahams-number/263884#263884 https://codegolf.stackexchange.com/questions/6430/shortest-t...

deleted 3y ago
[deleted]

pixl97 3y ago

Not exactly related, but still a fun article that covers tetration and how stupidly big simple systems can get. https://waitbutwhy.com/2014/11/1000000-grahams-number.html https://waitbutwhy.com/2014/11/1000000-grahams-number.html

lowbloodsugar 3y ago

So for those not familiar, 2^^4 is not ((2^2)^2)^2, it's 2^(2^(2^2)). So 2^5 is 2^65536. 2^6 is 2^(2^65536).

ninju 3y ago
corrections on the last sentence (I believe you forgot the extra ^s) 2^^5 is 2^65536. 2^^6 is 2^(2^65536).
- lowbloodsugar 3y ago
  Doh! I did yes! Thanks!

Jeff_Brown 3y ago

Why is it so hard?

eru 3y ago
Combinatorics and integers are hard. If you allowed fractional exchanges, this problem becomes easily solvable in polynomial time.
beders 3y ago
I think the issue is that the set of "operations" you can do on the start vector is limited.

renewiltord 3y ago

Interesting result. That's far faster growing than I would have anticipated since it seems intuitively like taking steps in a n-dimensional space which does grow fast, just not in a tetrative sense.

bgribble 3y ago

So given a start state and a library of valid transitions, it's easy to create a (target, path, destination) tuple that's valid (if you don't care what the destination is). It's easy to check if a (target, path, destination) tuple is valid. It's just really hard to find the path given just the target and the destination. This sounds like it has properties in common with "multiply two very large primes to create a very large composite number". Could any of this math be used as the basis for a cryptosystem?

duleee 3y ago
Reminds me of this: https://en.wikipedia.org/wiki/Lattice-based_cryptography https://en.wikipedia.org/wiki/Lattice-based_cryptography
- x3n0ph3n3 3y ago
  That's immediately what I thought of and was perplexed why the word "lattice" was nowhere in that article.
WorldMaker 3y ago
That description sounds similar to me of Elliptic Curve cryptography, as well. Pathfinding/curvefitting between two or more points in a curve without knowing other specifics of the curve.
SuchAnonMuchWow 3y ago
Depending on your library of valid transition, it could be really easy to find a path. That's the issue: there are libraries of paths where finding a path is really hard, but libraries where finding a path is easy. Say in another way, we know only the worst case complexity, not the complexity of a test case taken randomly. Some latices-based cryptosystems have such properties: there are theorems showing that if there is an algorithm good at solving random cases, than you can derive from it an algorithm good at solving any cases, including the worst ones. So for those problems, the worst case complexity is the same than the "average/random case" complexity.

hwayne 3y ago

This problem has a deep connection to formal methods: one of the first formal models of concurrent computing was Petri nets, which are equivalent to VASes. Petri nets are very limited in what they can model, and so finding reachability even those tiny, limited programs is HACK-complete! What I love so much about this is that it's really hard to find intuitive examples of TOWER-complete or even 2-EXPTIME-complete programs, but this one is so much harder than all of them but can easily be explained to a fifth-grader. Next goal is to find an intuitive HYPERACK problem...

7373737373 3y ago

The concept of reachability is pretty interesting in general as well. "Can a spaceship with a certain delta-v reach another planet within an n-body system? (And if so, what is the fastest-to target/most resource preserving acceleration schedule?)" - apparently necessitates brute force, practically not computable on long time scales due to the chaos inherent in n-body systems (https://space.stackexchange.com/questions/64392/escaping-earth-how-could-one-attempt-to-find-the-best-solution-to-this-traject https://space.stackexchange.com/questions/64392/escaping-ear..., https://en.wikipedia.org/wiki/N-body_problem https://en.wikipedia.org/wiki/N-body_problem) "Can a math proof be reached (within a certain number of proof steps) from the axioms?" - equivalent to the halting problem in most practical systems (https://math.stackexchange.com/questions/3477810/estimating-meta-mathematical-properties-of-conjectures https://math.stackexchange.com/questions/3477810/estimating-...) "Can a demoscene program with a very limited program size visualize (or codegolf program output) something specific?" - asking for nontrivial properties like this usually requires actually running each program, and there are unfathomably many short programs (https://www.dwitter.net/ https://www.dwitter.net/ is a good example of this) "In cookie-clicker games, is it possible to go above a certain score within a certain number of game ticks using some sequence of actions?" - in all but the simplest and shortest games (like https://qewasd.com https://qewasd.com), this is at least not efficiently (optimally) solvable using MILP and the like, as the number of possible action sequences increases exponentially And yet, despite these being really hard (or in the general case, impossible) problems, humans use some heuristics to achieve progress

westurner 3y ago
Quantum Discord: https://en.wikipedia.org/wiki/Quantum_discord https://en.wikipedia.org/wiki/Quantum_discord Quantum nonlocality: https://en.wikipedia.org/wiki/Quantum_nonlocality https://en.wikipedia.org/wiki/Quantum_nonlocality Butterfly effect -> Quantum chaos: https://en.wikipedia.org/wiki/Quantum_chaos https://en.wikipedia.org/wiki/Quantum_chaos -> Perturbation theory: https://en.wikipedia.org/wiki/Perturbation_theory_(quantum_mechanics) https://en.wikipedia.org/wiki/Perturbation_theory_(quantum_m... But then entropy in fluids, Satisfiability > Model Theory: https://en.wikipedia.org/wiki/Satisfiability https://en.wikipedia.org/wiki/Satisfiability Goal programming: https://en.wikipedia.org/wiki/Goal_programming https://en.wikipedia.org/wiki/Goal_programming And, ultimately, Self play (AlphaZero, ) https://en.wikipedia.org/wiki/Self-play https://en.wikipedia.org/wiki/Self-play "Q: LLM and/or an RL agent trained on [Lean mathlib] and tests" https://github.com/leanprover-community/mathlib/issues/17919 https://github.com/leanprover-community/mathlib/issues/17919

swader999 3y ago

I often wonder if the math for evolution is a similar problem. There's only a limited string of code that will survive and thrive. There's a set of evolutionary milestones or versions that need to happen to get where we are. There's a fixed amount of time on earth or perhaps the universe. Is there really enough time for all those dice roles?

eru 3y ago
I'm not sure what you are aiming at? Most of the competition in life comes from other living things. So any organism's failure to survive and thrive is often because some other organism is stealing their lunch money. But the 'lunch money' (eg a spot in the sunlight) doesn't disappear. > There's a fixed amount of time on earth or perhaps the universe. For the universe: it looks like the universe will expand forever, and more and more of it will recede behind the cosmological event horizon (because places that are far enough away will recede faster from us than the speed of light). The amount of usable energy within the spacetime we can reach is most likely finite. (Where 'usable energy' include considerations of entropy.) Time might be unlimited in an endlessly expanding universe, but usable energy ain't. But here's the savings grace: as far as we can tell, the physical lower limit of usable energy required for doing computations is proportional to the prevailing temperature. And expansion decreases the temperature of space, or rather its background radiation. So if you have 1J of energy left in your civilisation, you can expand half of it now to do some unit of computation. Then you wait until the temperature of your corner of the universe has dropped in half, and you expend another half of your remaining energy (1/4 J), to do another unit of computation. You can in principle keep doing this indefinitely, and get an infinite amount of computation. You can use that computation to power eg a simulation of life. --- Of course, this assumes you have found materials or mechanisms to run your computation on that can persist for arbitrary amounts of time in stasis without decay or using energy. The lower limit of energy usage for computation also only applies for irreversible computation. Reversible computation can be had for free, in principle. With long enough timescales, Boltzmann brains or even Boltzmann planets or Boltzmann galaxies also become a consideration.

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 ago
Would 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 ago
  If 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 ago
    If 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 ago
      Yes, 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 ago
Allowing 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.

Rapzid 3y ago

Kind of a bad way of explaining it to people familiar with reducing problems to reachability so they can be solved efficiently lol.

dclowd9901 3y ago

> “That’s a very natural restriction for a model of reality,” said Wojciech Czerwiński, a computer scientist at the University of Warsaw. “You cannot have a negative number of apples.” I realize this is probably outside the interest bounds of the problem space, but I could indeed have negative apples if I owe someone apples I don’t have.

dragonwriter 3y ago
No, then you would have however many apples you actually have, as well as an obligation to provide someone more apples than you have. Having an obligation to provide a thing is not actually the same thing as having negative one of the thing, even though it may occasionally be useful for some purposes to treat them as the same thing. (This is somewhat less true with money and things that work like it, since those things are essentially themselves already a social exoectation of future goods and services from other people, so the difference between an obligation of money and actual money is somewhat less than with other things.)