<p>The proof is given in Section 6 the <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.4144" rel="nofollow noreferrer">full version of the paper</a>. I bring an excerpt, since there was originally much confusion about what "fooling set" means.</p>

<p>Basically, the notion of fooling set was introduced by Jean-Camille Birget in <a href="http://dx.doi.org/10.1016/0020-0190(92)90198-5" rel="nofollow noreferrer">Intersection and union of regular languages and state complexity</a>.</p>

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

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

<hr>

<p><a href="https://i.sstatic.net/GcLYf.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GcLYf.png" alt="excerpt of the paper"></a></p>

CC BY-SA 2.5
2010-12-04T22:31:37.733Z
Thank you very much! I see the version from google book of the proceeding papers, and seems they omitted the proof part.
Handman
CC BY-SA 2.5
2010-12-04T23:24:06.030Z
@Handman: Since this is exactly the answer you were looking for, I think you should accept it!
Michael Blondin
CC BY-SA 2.5
2010-12-05T01:00:42.603Z
@Handman: You're welcome, but you misunderstood me. What I meant is that you should click on the green arrow next to the answer.
Michael Blondin
CC BY-SA 2.5
2010-12-05T01:13:58.563Z
@Handman: That was funny dude :)
Sadeq Dousti
CC BY-SA 2.5
2010-12-05T01:43:51.450Z
@Michael, sorry for misunderstanding you. This is the first time I asked question.
Handman
CC BY-SA 2.5
2010-12-05T23:46:59.600Z
The "official" preliminary full version is available as ECCC report ECCC TR06-027 under http://www.eccc.uni-trier.de/report/2006/027/
Hermann Gruber
CC BY-SA 4.0
2010-12-04T22:03:09.400Z
2019-01-05T18:27:07.043Z
2019-01-05T18:27:07.043Z
Sadeq Dousti
<p>I read in a <a href="https://doi.org/10.1007/11779148_33" rel="nofollow noreferrer">paper</a> 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.</p>
<p>Thank you.</p>
<p><strong>Edit:</strong> The fooling set technique is defined by the following theorem:</p>
<img src="https://i.sstatic.net/lzaAe.png" />

CC BY-SA 2.5
2010-12-04T20:50:34.817Z
Can you please identify the paper?
Mark Reitblatt
CC BY-SA 2.5
2010-12-04T21:00:40.273Z
Finding lower bounds for Nondeterministic state complexity is hard
Handman
CC BY-SA 2.5
2010-12-04T21:34:42.567Z
@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.
Handman
CC BY-SA 2.5
2010-12-04T21:35:06.290Z
@Handman: Please define the problem!
Michael Blondin
CC BY-SA 2.5
2010-12-04T21:36:32.363Z
Prove fooling set problem is NP-hard
Handman
CC BY-SA 2.5
2010-12-04T21:38:36.770Z
@Handman: But what is the fooling set problem?
Michael Blondin
CC BY-SA 2.5
2010-12-04T21:41:02.297Z
Using fooling set technique to find the lower bound
Handman
CC BY-SA 2.5
2010-12-04T21:43:39.807Z
@Handman: I don't see how this comment answers my question. Please make an effort to define the fooling set problem in your question if you expect people to take their time to help you!
Michael Blondin
CC BY-SA 2.5
2010-12-04T21:51:57.533Z
@Handman @Michael: I added the definition of the "fooling set" technique.
Sadeq Dousti
CC BY-SA 2.5
2010-12-04T21:59:42.890Z
@Sadeq: You probably should add the problem's definition given here: http://books.google.com/books?id=mTtp6FSH3-oC&pg=PA370&lpg=PA370&dq=fooling+set+problem&source=bl&ots=kdSnkrw6PA&sig=-nFwofxzPzWHSVtVmljqcysr8T0&hl=fr&ei=TLn6TPrAJsKAlAeywaiFDA&sa=X&oi=book_result&ct=result&resnum=4&ved=0CDEQ6AEwAw#v=onepage&q&f=false.
Michael Blondin
CC BY-SA 2.5
2010-12-04T22:04:43.677Z
@Michael: Thanks. The full (fool?!) definition of the problem, as well as the proof, comes below in my answer.
Sadeq Dousti
<reductions>
How to prove fooling set problem to be NP-hard
Handman
# How to prove fooling set problem to be NP-hard

(Asked by: username_0 on 2010-12-04)

I read in a [paper](https://doi.org/10.1007/11779148_33) 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:

![](https://i.sstatic.net/lzaAe.png)

**Tags:** reductions
> **Comments:**
> **username_1**: Can you please identify the paper?  
> **username_0**: Finding lower bounds for Nondeterministic state complexity is hard  
> **username_0**: @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.  
> **username_2**: @Handman: Please define the problem!  
> **username_0**: Prove fooling set problem is NP-hard  
> **username_2**: @Handman: But what is the fooling set problem?  
> **username_0**: Using fooling set technique to find the lower bound  
> **username_2**: @Handman: I don't see how this comment answers my question. Please make an effort to define the fooling set problem in your question if you expect people to take their time to help you!  
> **username_3**: @Handman @Michael: I added the definition of the "fooling set" technique.  
> **username_2**: @Sadeq: You probably should add the problem's definition given here: http://books.google.com/books?id=mTtp6FSH3-oC&pg=PA370&lpg=PA370&dq=fooling+set+problem&source=bl&ots=kdSnkrw6PA&sig=-nFwofxzPzWHSVtVmljqcysr8T0&hl=fr&ei=TLn6TPrAJsKAlAeywaiFDA&sa=X&oi=book_result&ct=result&resnum=4&ved=0CDEQ6AEwAw#v=onepage&q&f=false.  
> **username_3**: @Michael: Thanks. The full (fool?!) definition of the problem, as well as the proof, comes below in my answer.  

---

## 1 answers

### Answer by username_3 on 2010-12-04. Score: 8 | Accepted answer

The proof is given in Section 6 the [full version of the paper](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.4144). 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](http://dx.doi.org/10.1016/0020-0190(92)90198-5).

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.

---

[![excerpt of the paper](https://i.sstatic.net/GcLYf.png)](https://i.sstatic.net/GcLYf.png)

> **Comments:**
> **username_0**: Thank you very much! I see the version from google book of the proceeding papers, and seems they omitted the proof part.  
> **username_2**: @Handman: Since this is exactly the answer you were looking for, I think you should accept it!  
> **username_2**: @Handman: You're welcome, but you misunderstood me. What I meant is that you should click on the green arrow next to the answer.  
> **username_3**: @Handman: That was funny dude :)  
> **username_0**: @Michael, sorry for misunderstanding you. This is the first time I asked question.  
> **username_4**: The "official" preliminary full version is available as ECCC report ECCC TR06-027 under http://www.eccc.uni-trier.de/report/2006/027/  

---

