<p>I believe the asker is looking for an unpublished manuscript of W.J. Masek entitled "Some NP-complete set covering problems". Apparently, this paper is (in)famous enough in its elusiveness to have made it into one of David Johnson's <a href="http://www2.research.att.com/~dsj/columns/col20.pdf">NP-completeness columns</a> in 1987:</p>

<blockquote>
  <p>Of those ‘‘unpublished manuscripts’’ and ‘‘personal communications’’ that
  have not yet seen the formal light of day, two in particular stand out. They were
  both originally cited in [G&amp;J], and between them they seem to have garnered
  more enquiries than all the others combined, sending me off to the copier repeatedly
  to fulfill requests. One was the 1978 manuscript ‘‘Some NP-complete
  set covering problems,’’ by William Masek, who was then at MIT but has since disappeared from the theory community.</p>
  
  <p>That paper contains the NP-completeness proofs for two problems of major
  importance in circuit and VLSI design. One was MINIMUM DISJUNCTIVE
  NORMAL FORM ([LO9] in [G&amp;J]) [...] The second, related NP-completeness
  result was for the problem RECTILINEAR PICTURE COMPRESSION ([SR25] in [G&amp;J]) [...]</p>
  
  <p>Before disappearing, Masek sent me a revised manuscript [28], but as far as I
  know the paper was never published. </p>
</blockquote>

CC BY-SA 2.5
2010-12-23T18:13:00.667Z
nice answer. much better than the question !
Suresh Venkat
CC BY-SA 2.5
2010-12-23T17:42:14.337Z
2010-12-23T19:13:40.423Z
2010-12-23T19:13:40.423Z
mhum
<p>I need a demonstration that the rectilinear picture compression is NP-hard, I know that this fact was proven using 3SAT by Masek in 1978 but I can't find the paper.</p>

CC BY-SA 2.5
2010-12-23T17:18:54.057Z
1. define the problem. 2. fix typos
Suresh Venkat
CC BY-SA 2.5
2010-12-23T19:45:22.237Z
Tell us what you already know so we can help you better.
Warren Schudy
CC BY-SA 2.5
2010-12-24T01:58:53.597Z
It seems to me that [this new user](http://cstheory.stackexchange.com/users/2914/amlv) is posting a list of homework questions, see [1](http://cstheory.stackexchange.com/questions/3960/i-am-looking-for-an-efficient-algorithm-to-solve-this-problem), [2](http://cstheory.stackexchange.com/questions/3957/prove-that-the-problem-of-rectilinear-picture-compression-is-np-complete), [3](http://cstheory.stackexchange.com/questions/3960/i-am-looking-for-an-efficient-algorithm-to-solve-this-problem). Voting to close. In addition the questions are not well-written.
Kaveh
<cc.complexity-theory><reference-request><np-hardness>
Prove that the problem of rectilinear picture compression is np-complete
amlv
# Prove that the problem of rectilinear picture compression is np-complete

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

I need a demonstration that the rectilinear picture compression is NP-hard, I know that this fact was proven using 3SAT by Masek in 1978 but I can't find the paper.

**Tags:** cc.complexity-theory, reference-request, np-hardness

> **Comments:**
> **username_1**: 1. define the problem. 2. fix typos  
> **username_2**: Tell us what you already know so we can help you better.  
> **username_3**: It seems to me that [this new user](http://cstheory.stackexchange.com/users/2914/username_0) is posting a list of homework questions, see [1](http://cstheory.stackexchange.com/questions/3960/i-am-looking-for-an-efficient-algorithm-to-solve-this-problem), [2](http://cstheory.stackexchange.com/questions/3957/prove-that-the-problem-of-rectilinear-picture-compression-is-np-complete), [3](http://cstheory.stackexchange.com/questions/3960/i-am-looking-for-an-efficient-algorithm-to-solve-this-problem). Voting to close. In addition the questions are not well-written.  

---

## 1 answers

### Answer by username_4 on 2010-12-23. Score: 16

I believe the asker is looking for an unpublished manuscript of W.J. Masek entitled "Some NP-complete set covering problems". Apparently, this paper is (in)famous enough in its elusiveness to have made it into one of David Johnson's [NP-completeness columns](http://www2.research.att.com/~dsj/columns/col20.pdf) in 1987:

> Of those ‘‘unpublished manuscripts’’ and ‘‘personal communications’’ that
> have not yet seen the formal light of day, two in particular stand out. They were
> both originally cited in [G&J], and between them they seem to have garnered
> more enquiries than all the others combined, sending me off to the copier repeatedly
> to fulfill requests. One was the 1978 manuscript ‘‘Some NP-complete
> set covering problems,’’ by William Masek, who was then at MIT but has since disappeared from the theory community.
>
> That paper contains the NP-completeness proofs for two problems of major
> importance in circuit and VLSI design. One was MINIMUM DISJUNCTIVE
> NORMAL FORM ([LO9] in [G&J]) [...] The second, related NP-completeness
> result was for the problem RECTILINEAR PICTURE COMPRESSION ([SR25] in [G&J]) [...]
>
> Before disappearing, Masek sent me a revised manuscript [28], but as far as I
> know the paper was never published.

> **Comments:**
> **username_1**: nice answer. much better than the question !  

---

