# How to prove fooling set problem to be NP-hard

I read in a paper showing that it can be implemented by reducing induced matching problem on bipartite graphs to fooling set. But the proof was omitted in that paper and I cannot find answer by myself.

Thank you.

Edit: The fooling set technique is defined by the following theorem:

• Can you please identify the paper? Dec 4 '10 at 20:50
• Finding lower bounds for Nondeterministic state complexity is hard Dec 4 '10 at 21:00
• @Michael: I did not find a good reduction to reduce a NP-hard to fooling set. I thought CLIQUE may be a good idea, but I failed to find the gardget. Dec 4 '10 at 21:34
• @Handman: Please define the problem! Dec 4 '10 at 21:35
• @Handman: But what is the fooling set problem? Dec 4 '10 at 21:38

The proof is given in Section 6 the full version of the paper. I bring an excerpt, since there was originally much confusion about what "fooling set" means.

Basically, the notion of fooling set was introduced by Jean-Camille Birget in Intersection and union of regular languages and state complexity.

To prove that fooling set problem (as defined below) is NP-hard, the authors reduced the NP-complete induced matching problem on bipartite graphs to it.

Here's an excerpt of the paper, which defines the problem and proves the theorem.

• Thank you very much! I see the version from google book of the proceeding papers, and seems they omitted the proof part. Dec 4 '10 at 22:31
• @Handman: Since this is exactly the answer you were looking for, I think you should accept it! Dec 4 '10 at 23:24
• @Handman: You're welcome, but you misunderstood me. What I meant is that you should click on the green arrow next to the answer. Dec 5 '10 at 1:00
• @Handman: That was funny dude :) Dec 5 '10 at 1:13
• @Michael, sorry for misunderstanding you. This is the first time I asked question. Dec 5 '10 at 1:43