Post History
Challenge Find a valid input (multiset of positive integers) for this deterministic $O(n^2)$ Partition algorithm such that: The algorithm fails to find a solution even though one exists, or The...
#2: Post edited
by
WheatWizard
·
2025-11-25T22:29:41Z (10 months ago)
Add MathJax formatting, fix typo
Partition Algorithm Trap
- **Challenge**
Find a valid input (multiset of positive integers) for this deterministic O(n)^2 Partition algorithm such that:- The algorithm fails to find a solution even though one exists, or
The algorithm exhibits Non polinomical runtime (e.g., exponential blowup).- The Partition problem: given a multiset of positive integers, is there a subset whose sum is exactly half of the total sum?
- The algorithm is here:
- https://osf.io/wemjy
- **Examples**
- Input: [1, 2, 3, 4]
- Output: Algorithm returns a solution subset: [1, 4] or [2, 3]
- Input: [1, 1, 1, 2, 3]
- Output: Algorithm fails or slows down (example for illustration)
- ⚠️ Any proposed input must have a solution. Inputs without a solution are not valid counterexamples.
- **Rules**
- The input is a multiset of positive integers.
- The algorithm may return any valid solution subset.
- **Goal**: break the algorithm by finding a solvable instance where it fails or is slow (It have to be exponential).
- Submissions may include explicit instances or families of inputs.
- Both constructive counterexamples and theoretical reasoning are welcome.
- Scoring: shortest or most elegant counterexample wins, with bonus for explanation.
- **Challenge**
- Find a valid input (multiset of positive integers) for this deterministic $O(n^2)$ Partition algorithm such that:
- The algorithm fails to find a solution even though one exists, or
- The algorithm exhibits Non polynomial runtime (e.g., exponential blowup).
- The Partition problem: given a multiset of positive integers, is there a subset whose sum is exactly half of the total sum?
- The algorithm is here:
- https://osf.io/wemjy
- **Examples**
- Input: [1, 2, 3, 4]
- Output: Algorithm returns a solution subset: [1, 4] or [2, 3]
- Input: [1, 1, 1, 2, 3]
- Output: Algorithm fails or slows down (example for illustration)
- ⚠️ Any proposed input must have a solution. Inputs without a solution are not valid counterexamples.
- **Rules**
- The input is a multiset of positive integers.
- The algorithm may return any valid solution subset.
- **Goal**: break the algorithm by finding a solvable instance where it fails or is slow (It have to be exponential).
- Submissions may include explicit instances or families of inputs.
- Both constructive counterexamples and theoretical reasoning are welcome.
- Scoring: shortest or most elegant counterexample wins, with bonus for explanation.
#1: Initial revision
by
KaoruAK
·
2025-10-07T16:39:41Z (12 months ago)
Partition Algorithm Trap
**Challenge** Find a valid input (multiset of positive integers) for this deterministic O(n)^2 Partition algorithm such that: The algorithm fails to find a solution even though one exists, or The algorithm exhibits Non polinomical runtime (e.g., exponential blowup). The Partition problem: given a multiset of positive integers, is there a subset whose sum is exactly half of the total sum? The algorithm is here: https://osf.io/wemjy **Examples** Input: [1, 2, 3, 4] Output: Algorithm returns a solution subset: [1, 4] or [2, 3] Input: [1, 1, 1, 2, 3] Output: Algorithm fails or slows down (example for illustration) ⚠️ Any proposed input must have a solution. Inputs without a solution are not valid counterexamples. **Rules** The input is a multiset of positive integers. The algorithm may return any valid solution subset. **Goal**: break the algorithm by finding a solvable instance where it fails or is slow (It have to be exponential). Submissions may include explicit instances or families of inputs. Both constructive counterexamples and theoretical reasoning are welcome. Scoring: shortest or most elegant counterexample wins, with bonus for explanation.