Remix.run Logo
ogogmad 5 days ago

Is the problem mentioned in the article equivalent to deciding whether there exists a solution to a system of linear equations in the positive integers?

I think no, because the vector additions are considered in sequence, and at no point are you allowed to leave the positive quadrant.

[Edit] Yeah, it's more than just solving positive integer linear systems: https://en.m.wikipedia.org/wiki/Vector_addition_system

hwayne 5 days ago | parent [-]

IIRC without that restriction the problem is "just" NP-complete.