3 ms·

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.

> 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.