←back to thread

108 points BerislavLopac | 1 comments | | HN request time: 0.282s | source
Show context
ogogmad ◴[] No.43718788[source]
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

replies(1): >>43720871 #
1. hwayne ◴[] No.43720871[source]
IIRC without that restriction the problem is "just" NP-complete.