Polyamory in the Spotlight
If you’ve been practicing CNM for a while you may have noticed that non-monogamy is having a moment in the spotlight right now. We won’t bother naming the latest TV show to misrepresent our community, because we assume that like us, you probably don’t care too much.
Polyamory Time Management
Your time is at a premium, and for many of us “google calendar is life”; so instead of articles detailing what the mainstream media is getting wrong about non-monogamy, today we’re bringing our polyamorous math nerds some news that (we hope) you can actually use.
Polyamorous Scheduling
A paper published by the University of Liverpool, UK has determined in precise mathematical terms exactly how hard polyamorous scheduling is, and TLDR: it’s really really hard.
No, like really.
To quote the abstract:
Finding schedules for pairwise meetings between the members of a complex social group without creating interpersonal conflict is challenging, especially when different relationships have different needs.
They concluded that:
We show that the problem is NP-hard
Your Polyamory Calendar
Okay, we need you to set aside that the letters “NP” usually mean “nesting partner” to our community. It’s just a fun coincidence that the math terminology happens to call problems of this calibur “NP-hard”. You were not the only one, if you read that as “nesting-partner-hard”, but that’s not what that means.
How hard is hard
If you lost us at the word math, don’t worry, all you need to know is that when ranking problem difficulty, “NP-hard” is considered… wait for it…. harder than “NP”.
Basically this classification has to do with two things, how long it takes a computer to calculate a solution to the problem, and also how long it takes to verify that the solution is valid.
If something is hard to calculate, but easy to verify it would be rated with a difficulty level of “NP”. However if it’s both hard to calculate and hard to verify, then the difficulty goes up a level to “NP-Hard”.
Harder than solving Sudoku
Compared to the task of solving a sudoku puzzle, poly calendaring is much harder. Sudoku only has a difficulty level of “NP” because it’s hard to solve, but once a solution is provided, that solution is comparatively easy to check.
The problem of poly calendaring is harder because it’s not just hard to find a solution, but once found, it’s also hard to verify that the solution is valid.
“NP-hard” describes:
“Class of problems which are at least as hard as the hardest problems in NP. Problems that are NP-hard do not have to be elements of NP; indeed, they may not even be decidable.”
Possibly impossible?
Did you catch the last part, “indeed, they may not even be decidable.” as in there may not always be a solution.
When it comes to your poly calendar, it’s not your imagination. Maybe you can’t be more creative with your time allocation, sometimes it might actually be mathematically impossible.
Accounting for neediness
To reach their conclusion, the researchers considered a set of fictional people, and paired them up into a polycule of intersecting couples using weights to rank importance like “neediness or emotional weight.”
They tried to find a periodic schedule that minimized the waiting time between meetings for each couple, with an assumption that each person could only meet with at most one partner per day.
By doing so they've now contributed the first nontrivial hardness-of-approximation reduction for any periodic scheduling problem. You can download or read the paper at https://arxiv.org/pdf/2403.00465.pdf
If you’re curious about the math, and the P versus NP problem, this Wikipedia page might be helpful. (We say might, because this is some high level math.)
Images: Pinwheel Photo by Nick Fewings on Unsplash, poly calendar meme by @PolyamPirates, and “Figure 1: An example Optimisation Polyamorous Scheduling instance with 8 persons” from Polyamorous Scheduling Gąsieniec et al.
