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.

  • 4
    $\begingroup$ 1. define the problem. 2. fix typos $\endgroup$ Dec 23 '10 at 17:18
  • 2
    $\begingroup$ Tell us what you already know so we can help you better. $\endgroup$ Dec 23 '10 at 19:45
  • $\begingroup$ It seems to me that this new user is posting a list of homework questions, see 1, 2, 3. Voting to close. In addition the questions are not well-written. $\endgroup$
    – Kaveh
    Dec 24 '10 at 1:58

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 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.

  • 7
    $\begingroup$ nice answer. much better than the question ! $\endgroup$ Dec 23 '10 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.