Technologist Mag
  • Home
  • Tech News
  • AI
  • Apps
  • Gadgets
  • Gaming
  • Guides
  • Laptops
  • Mobiles
  • Wearables
  • More
    • Web Stories
    • Trending
    • Press Release

Subscribe to Updates

Get the latest tech news and updates directly to your inbox.

What's On

OpenAI Reportedly Working On an AI-Powered Web Browser, to Compete With Google Chrome

10 July 2025

Tecno Pova 7 5G, Pova 7 Pro 5G With Dimensity 7300 Ultimate SoC Sale in India Starts Today: Price, Offers

10 July 2025

A New Kind of AI Model Lets Data Owners Take Control

10 July 2025

Gemini Rolls Out to Wear OS Smartwatches With Support for Natural Language Commands

10 July 2025

Apple Reportedly Working on Sealed-Device Update System for MacBook Units at Apple Stores

10 July 2025
Facebook X (Twitter) Instagram
Facebook X (Twitter) Instagram
Technologist Mag
SUBSCRIBE
  • Home
  • Tech News
  • AI
  • Apps
  • Gadgets
  • Gaming
  • Guides
  • Laptops
  • Mobiles
  • Wearables
  • More
    • Web Stories
    • Trending
    • Press Release
Technologist Mag
Home » Why Pigeons at Rest Are at the Center of Complexity Theory
Tech News

Why Pigeons at Rest Are at the Center of Complexity Theory

By technologistmag.com4 May 20253 Mins Read
Share
Facebook Twitter Reddit Telegram Pinterest Email

By January 2020, Papadimitriou had been thinking about the pigeonhole principle for 30 years. So he was surprised when a playful conversation with a frequent collaborator led them to a simple twist on the principle that they’d never considered: What if there are fewer pigeons than holes? In that case, any arrangement of pigeons must leave some empty holes. Again, it seems obvious. But does inverting the pigeonhole principle have any interesting mathematical consequences?

It may sound as though this “empty-pigeonhole” principle is just the original one by another name. But it’s not, and its subtly different character has made it a new and fruitful tool for classifying computational problems.

To understand the empty-pigeonhole principle, let’s go back to the bank-card example, transposed from a football stadium to a concert hall with 3,000 seats—a smaller number than the total possible four-digit PINs. The empty-pigeonhole principle dictates that some possible PINs aren’t represented at all. If you want to find one of these missing PINs, though, there doesn’t seem to be any better way than simply asking each person their PIN. So far, the empty-pigeonhole principle is just like its more famous counterpart.

The difference lies in the difficulty of checking solutions. Imagine that someone says they’ve found two specific people in the football stadium who have the same PIN. In this case, corresponding to the original pigeonhole scenario, there’s a simple way to verify that claim: Just check with the two people in question. But in the concert hall case, imagine that someone asserts that no person has a PIN of 5926. Here, it’s impossible to verify without asking everyone in the audience what their PIN is. That makes the empty-pigeonhole principle much more vexing for complexity theorists.

Two months after Papadimitriou began thinking about the empty-pigeonhole principle, he brought it up in a conversation with a prospective graduate student. He remembers it vividly, because it turned out to be his last in-person conversation with anyone before the Covid-19 lockdowns. Cooped up at home over the following months, he wrestled with the problem’s implications for complexity theory. Eventually he and his colleagues published a paper about search problems that are guaranteed to have solutions because of the empty-pigeonhole principle. They were especially interested in problems where pigeonholes are abundant—that is, where they far outnumber pigeons. In keeping with a tradition of unwieldy acronyms in complexity theory, they dubbed this class of problems APEPP, for “abundant polynomial empty-pigeonhole principle.”

One of the problems in this class was inspired by a famous 70-year-old proof by the pioneering computer scientist Claude Shannon. Shannon proved that most computational problems must be inherently hard to solve, using an argument that relied on the empty-pigeonhole principle (though he didn’t call it that). Yet for decades, computer scientists have tried and failed to prove that specific problems are truly hard. Like missing bank-card PINs, hard problems must be out there, even if we can’t identify them.

Historically, researchers haven’t thought about the process of looking for hard problems as a search problem that could itself be analyzed mathematically. Papadimitriou’s approach, which grouped that process with other search problems connected to the empty-pigeonhole principle, had a self-referential flavor characteristic of much recent work in complexity theory—it offered a new way to reason about the difficulty of proving computational difficulty.

Share. Facebook Twitter Pinterest LinkedIn Telegram Reddit Email
Previous ArticleI’ll buy the Pixel Watch 4 if Google changes this one feature
Next Article All Borderlands games in order, by release date and chronologically

Related Articles

A New Kind of AI Model Lets Data Owners Take Control

10 July 2025

Our Favorite Dyson Vacuum (and Its Mop Version!) Is $200 Off Right Now

10 July 2025

Elon Musk Unveils Grok 4 Amid Controversy Over Chatbot’s Antisemitic Posts

10 July 2025

McDonald’s AI Hiring Bot Exposed Millions of Applicants’ Data to Hackers Who Tried the Password ‘123456’

10 July 2025

This Camera-Equipped Automatic Litter Box Is a Prime Day Deal

10 July 2025

The ‘Click-to-Cancel’ Rule Was Killed, but Consumer Advocates Could Revive It

10 July 2025
Stay In Touch
  • Facebook
  • Twitter
  • Pinterest
  • Instagram
  • YouTube
  • Vimeo

Subscribe to Updates

Get the latest tech news and updates directly to your inbox.

Don't Miss

Tecno Pova 7 5G, Pova 7 Pro 5G With Dimensity 7300 Ultimate SoC Sale in India Starts Today: Price, Offers

By technologistmag.com10 July 2025

Tecno Pova 7 5G series sale in India begins today. The lineup was launched on…

A New Kind of AI Model Lets Data Owners Take Control

10 July 2025

Gemini Rolls Out to Wear OS Smartwatches With Support for Natural Language Commands

10 July 2025

Apple Reportedly Working on Sealed-Device Update System for MacBook Units at Apple Stores

10 July 2025

Samsung Galaxy S25 FE Design Appears on WPC Database; May Support Qi2 Wireless Charging

10 July 2025
Technologist Mag
Facebook X (Twitter) Instagram Pinterest
  • Privacy
  • Terms
  • Advertise
  • Contact
© 2025 Technologist Mag. All Rights Reserved.

Type above and press Enter to search. Press Esc to cancel.