PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
The problem is more commonly known as the necklace splitting problem that is often told with thieves trying to split a necklace with an even number of each jewel type so the two thieves get the same number of each jewel. Currently, no polynomial-time algorithm is known but is also not known to be NP-hard. There is one very interesting result concerning this problem. If d is the number of istinct ingredients/jewel types, then there is a way to cut the sandwich/necklace using at most d cuts [1]. However, the proof is non-constructive and does not provide a polynomial-time algorithm for finding these cuts. To get an idea what flavor these non-constructive are, it follows from the Borsuk-Ulam theorem which is like a very powerful generalization of Brouwer’s fixed-point theorem to higher dimensions.
The problem is known to be in PPAD [2] which roughly means that there is an algorithm that will find a solution using at most d cuts that
is, in some sense, similar in spirit to the Simplex algorithm for solving linear programs. The Wikipedia page on PPAD is a decent
starting point to learn more about problems in PPAD [3] if you are curious. It is an interesting complexity class between P and NP. There
is a notion of a problem being PPAD-complete and an interesting open problem is to determine if the necklace splitting problem is PPAD-complete or not.
- Alon, Noga; West, D. B. (December 1986). “The Borsuk-Ulam theorem and bisection of necklaces”. Proceedings of the American Mathematical
Society 98 (4 pages=623-628). - Christos Papadimitriou (1994). “On the complexity of the parity argument and other inefficient proofs of existence”. Journal of Computer and System Sciences 48 (3): 498-532. doi:10.1016/S0022-0000(05)80063-7
- http://en.wikipedia.org/wiki/PPAD
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.