[Cs4800] Fwd: Efficiently Constructive Inclusion Exclusion

[Karl Lieberherr]

This gives some more insight into your current homework problem.

A discussion with a professor in Israel, currently at Harvard.

-- Karl
---------- Forwarded message ----------
From: Alex Samorodnitsky <salex at cs.huji.ac.il>
Date: Fri, Feb 12, 2010 at 3:20 AM
Subject: Re: Efficiently Constructive Inclusion Exclusion
To: Karl Lieberherr <lieber at ccs.neu.edu>
Cc: Emanuele Viola <viola at ccs.neu.edu>


Hi Karl,

I am happy to hear that you have solved the question. Do I understand
correctly, that the combinatorial structure is what saves the day and
makes efficient search possible?

I didn't have any well-defined conjecture, but rather a vague (and
probably trivial) feeling that having only the decision version as a
black-box shouldn't lead to efficient search, in general. Say, just
the fact that we know that the intersection of two sets lying in an
exponential-size ambient set, shouldn't lead to an efficient search
procedure.

As far as I remember, when we discussed this with Emanuele, before we
went out for dinner, Emanuele pointed out, that this indeed should be
the case. Abstracting out even more, suppose we have a subset A of an
exponential-size set that we know is non-empty, and we also have an
efficient membership procedure w.r.t. to A. This shouldn't lead to
finding an element of A.

Best wishes,

Alex


On Thu, Feb 11, 2010 at 11:28 AM, Karl Lieberherr <lieber at ccs.neu.edu>
wrote:
> Hi Alex:
>
> We talked about the LeafCovering problem which is coNP-complete but
> LeafCovering(k)
> for fixed k is in P by a not-efficiently-constructive counting technique
> using the inclusion/exclusion
> principle. LeafCovering(k) is a decision problem.
>
> We then asked the question: is the search version, called
FLeafCovering(k),
> polynomial?
> In other words, can we make the not-efficiently-constructive counting
> technique efficiently constructive?
>
> Your conjecture was, that in general, the search version should still be
> NP-hard.
> You had some hope that for our special case, we might succeed with showing
> that FLeafCovering(k) is polynomial
> because of the additional structure we have.
>
> You were right: we have shown that FLeafCovering is in FP. The proof does
> not use LeafCovering(k) as a blackbox.
> It uses the inclusion-exclusion principle in a more clever way.
>
> Could you tell us a liitle more about your conjecture? You made some
> informal argument to
> Emanuele that I did not follow in detail. That might make our result more
> interesting.
>
> Take care,
> -- Karl
-------------- next part --------------
HTML attachment scrubbed and removed