CODEWITHSUNDEEP
algorithmnp-complete
theimpatientcoder
theimpatientcoder

Reputation: 1098

How can I explain the meaning of "exact cover "

I want to explain the exact cover problem to my colleagues who don't have any mathematical background as such. I want to explain them where it can be used and how? So my question goes like this: How can I explain the exact cover problem to someone who don't have a mathematical background or rather to children and make it more interesting and intuitive? With this I also want to explain the concept of P-NP (in general) as well.

Upvotes: 0

Views: 558

Answers (2)

Jean-Baptiste Yunès
Jean-Baptiste Yunès

Reputation: 36431

Each people having a phone number directory of others inside the same city, is it possible to find a set of people such that every phone number is catched (covers all phone numbers) and only once (exact).

Upvotes: 0

shapiro yaacov
shapiro yaacov

Reputation: 2346

I think a good analogy here is a puzzle.

Let's say there is a square on the floor you want to cover, but instead of having the regular setup where you have the exact amount and shapes to cover it once and they all fit in a certain way, you have enough pieces to cover it many times.

The problem is to find a bunch of pieces that:
A. They all fit together (no overlaps, no gaps).
B. They cover the right surface area (the square you have).

Upvotes: 1

Related Questions