4 ms·

> effectively finite This made me scratch my head a bit. I'm aware of there being different types of infinities, but to call a "smaller" infinity "effectively

> effectively finite This made me scratch my head a bit. I'm aware of there being different types of infinities, but to call a "smaller" infinity "effectively finite" seems a bit odd. I'm not up-to-date on math terminology, though. In truth, I'm not quite sure what you mean by "solvable" vs "not solvable" here, either. In the above discussion I thought it meant "not tractable in a reasonable amount of time" (i.e. NP-complete => "not solvable"). But you seem to have a different definition you're working from. Could you elaborate on what you mean by "effectively finite => solvable" ?

layer8 4y ago
It is effectively finite in that the knapsack has a finite capacity and there is a finite selection of items with positive weight, hence the number of items that can fit into the knapsack is limited by the knapsack capacity divided by the smallest item weight. So, while for the unbounded knapsack problem the number of instances of an item that may be included is not limited, it is effectively still limited by the knapsack capacity. Therefore the number of item combinations that have to be considered is finite as well. The GP had put "solvable" in quotes. I understood the GP to say that for space planning, there may not be an algorithm that is guaranteed to produce an answer in finite time. For the knapsack problem there is such an algorithm (even if that finite time, due to NP-completeness, could be very long). The formal term "solvable", as applied to decision problems, actually only means "semidecidable", a much weaker property, see https://en.wikipedia.org/wiki/Decision_problem#Decidability https://en.wikipedia.org/wiki/Decision_problem#Decidability.
deleted 4y ago
[deleted]
SamBam 4y ago
The knapsack problem has a finite number of solutions. You can brute-force the optimal solution, if you don't care about efficiency. Ditto the Traveling Salesman problem. I'm not sure whether this problem is finite or not, given that you can place objects at any real-number coordinates and any real-number angle. But if you simply make those increments small enough (you can only put boxes a whole number of planck-lengths apart) then there are a finite number of possible arrangements, so it's possible to brute-force.

layer8 4y ago

It is effectively finite in that the knapsack has a finite capacity and there is a finite selection of items with positive weight, hence the number of items that can fit into the knapsack is limited by the knapsack capacity divided by the smallest item weight. So, while for the unbounded knapsack problem the number of instances of an item that may be included is not limited, it is effectively still limited by the knapsack capacity. Therefore the number of item combinations that have to be considered is finite as well. The GP had put "solvable" in quotes. I understood the GP to say that for space planning, there may not be an algorithm that is guaranteed to produce an answer in finite time. For the knapsack problem there is such an algorithm (even if that finite time, due to NP-completeness, could be very long). The formal term "solvable", as applied to decision problems, actually only means "semidecidable", a much weaker property, see https://en.wikipedia.org/wiki/Decision_problem#Decidability https://en.wikipedia.org/wiki/Decision_problem#Decidability.

deleted 4y ago

[deleted]

SamBam 4y ago

The knapsack problem has a finite number of solutions. You can brute-force the optimal solution, if you don't care about efficiency. Ditto the Traveling Salesman problem. I'm not sure whether this problem is finite or not, given that you can place objects at any real-number coordinates and any real-number angle. But if you simply make those increments small enough (you can only put boxes a whole number of planck-lengths apart) then there are a finite number of possible arrangements, so it's possible to brute-force.