• Home
  • Motorcycles
  • Electric Motorcycles
  • 3 wheelers
  • FUV Electric 3 wheeler
  • Shop
  • Listings

Subscribe to Updates

Get the latest creative news from CycleNews about two, three wheelers and Electric vehicles.

What's Hot

How the Farm Industry Spied on Animal Rights Activists and Pushed the FBI to Treat Them as Terrorists

“Mario Kart World” Devs Broke Their Own Rule on Who Gets to Drive

‘Mario Kart World’ Races Are More Chaotic—and Better—Than Ever

Facebook Twitter Instagram
  • Home
  • Motorcycles
  • Electric Motorcycles
  • 3 wheelers
  • FUV Electric 3 wheeler
  • Shop
  • Listings
Facebook Twitter Instagram Pinterest
Cycle News
Submit Your Ad
Cycle News
You are at:Home » Why Pigeons at Rest Are at the Center of Complexity Theory
Electric Motorcycles

Why Pigeons at Rest Are at the Center of Complexity Theory

cycleBy cycleMay 4, 202503 Mins Read
Share Facebook Twitter Pinterest LinkedIn Tumblr Email
Share
Facebook Twitter LinkedIn 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.



Source link

Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
Previous ArticleThe Phony Physics of Star Wars Are a Blast
Next Article 9 Great Deals on Mother’s Day Gifts (2025)
cycle
  • Website

Related Posts

How the Farm Industry Spied on Animal Rights Activists and Pushed the FBI to Treat Them as Terrorists

June 3, 2025

“Mario Kart World” Devs Broke Their Own Rule on Who Gets to Drive

June 3, 2025

‘Mario Kart World’ Races Are More Chaotic—and Better—Than Ever

June 3, 2025
Add A Comment

Leave A Reply Cancel Reply

You must be logged in to post a comment.

Demo
Top Posts

How the Farm Industry Spied on Animal Rights Activists and Pushed the FBI to Treat Them as Terrorists

June 3, 2025

The urban electric commuter FUELL Fllow designed by Erik Buell is now opening orders | thepack.news | THE PACK

July 29, 2023

2024 Yamaha Ténéré 700 First Look [6 Fast Facts For ADV Riding]

July 29, 2023
Stay In Touch
  • Facebook
  • YouTube
  • TikTok
  • WhatsApp
  • Twitter
  • Instagram
Latest Reviews

Subscribe to Updates

Get the latest tech news from FooBar about tech, design and biz.

Demo
Most Popular

How the Farm Industry Spied on Animal Rights Activists and Pushed the FBI to Treat Them as Terrorists

June 3, 2025

The urban electric commuter FUELL Fllow designed by Erik Buell is now opening orders | thepack.news | THE PACK

July 29, 2023

2024 Yamaha Ténéré 700 First Look [6 Fast Facts For ADV Riding]

July 29, 2023
Our Picks

OpenAI Cofounder Reid Hoffman Gives Sam Altman a Vote of Confidence

How to Use ‘Circle to Search’ on an Android Phone

Bhārat Bikes: Hero’s Mavrick 440 vs. Harley’s X440

Subscribe to Updates

Get the latest news from CycleNews about two, three wheelers and Electric vehicles.

© 2025 cyclenews.blog
  • Home
  • About us
  • Get In Touch
  • Shop
  • Listings
  • My Account
  • Submit Your Ad
  • Terms & Conditions
  • Stock Ticker

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