Algebraist Discovers Wedding Seating Chart Is NP-Hard, Cancels Reception

A computational algebraist has cancelled her wedding reception after proving that the seating chart, given the constraints imposed by her extended family, constitutes an NP-hard optimization problem for which no efficient solution exists. Dr. Clara Polynomial, 32, began the seating arrangement as a weekend task six weeks before her wedding. By week three, she had formalized it as a constraint satisfaction problem and proven a reduction from 3-SAT. "There are 120 guests, fourteen known feuds, three dietary restrictions that correlate with political affiliations, two ex-couples who cannot be at the same table, and my mother, who has vetoed every configuration that doesn't place her adjacent to the head table but not at the head table," Polynomial enumerated. "I mapped the constraints to a Boolean satisfiability instance and proved it's NP-hard. There is no polynomial-time algorithm that produces a valid seating chart for this family." Her fiance, accountant David Linear, suggested they simply place people wherever seemed reasonable and deal with any issues as they arose. "He proposed a greedy algorithm," Polynomial said, visibly distressed. "For an NP-hard problem. A greedy algorithm provides no approximation guarantee. Uncle Victor could end up next to Aunt Margaret. The consequences would be exponential." The couple has replaced the sit-down reception with a cocktail-style event where guests stand and circulate freely, which Polynomial describes as "a randomized solution that distributes conflict probabilistically across time rather than concentrating it spatially." Her mother has objected to the standing format on the grounds that she "didn't buy new shoes to stand in them." Polynomial has noted that her mother's shoe constraint was not included in the original problem formulation and may, in fact, be the constraint that makes the problem infeasible. The couple will marry in June as planned. The reception will feature no assigned seating, no speeches, and a bar that Polynomial describes as "the only tractable part of this entire event."