![[-]](/~ygleyzer/course.wiki/images/button-minus.gif)
Q2: polynomiality (is that even a word?) of the reduction
Re: Q2: polynomiality (is that even a word?) of the reduction
Re: Q2: polynomiality (is that even a word?) of the reduction Thank you for your answer, however:
Another question:
If I reduce an instance of a Set Cover(S,k) problem to an instance of a Base(G,k) problem, where the graph G has |V| vertices, and |V|>L (L is the number of sets in the Set Cover problem), then this reduction is no good, because I can get a base of size |V|, but I can never get a Set Cover the size of |V| because I don't have enough sets (|V|>L). So the <=> equivilence doesn't hold. The same holds if |V|<L, the other way around, I don't have enough vertices to form a Base the size of L.
This stems from the requirement that we need to find the answer to an ARBITRARY k, and k can be equal to |V| or L.
This means that we need to reduce a Set Cover problem over L vertices to an instance of a Base problem, where the graph G has EXACTLY L vertices. No? I don't think it's possible...
In all the descriptions of the Vertex Cover problem or the Set Cover problem I've seen online the goal is to find a minimal k, not an arbitrary one. The difference here is critical. That's why I think this problem in its current formulation is unsolvable. Please correct me if I'm wrong.
Thanks.
Re: Q2: polynomiality (is that even a word?) of the reduction זה בדיוק מה שרציתי לשאול -
האם האלגוריתם לפתרון בעיית Set-Cover יכול להשליך מהחלון מופעים בהם k>L, כלומר מופעים בהם אנו מתבקשים לכסות את U עם יותר קבוצות מכמה שבכלל יש לנו? זה חשוב, כי לפעמים להעביר k כזה לרדוקציה יכול, כפי שנאמר לעיל, לסבך אותנו סתם.
נ.ב. לא איכפת לנו להתפשר ולהעביר, למשל, k=0 לאלגוריתם שיפתור את Base, על-מנת לתקוע לו מקל בגלגלים. ההנחה שלנו היא שזה בסדר - אם מותר לקחת את תתי הקבוצות ולערבב אותם, להכניס לתנור ולקבל גרף, אז מה זה לעשות איזה שינוי קטן ב-k...
תודה!
Re: Q2: polynomiality (is that even a word?) of the reduction Let us denote the language for SetCover by L.
Let us denote the language for Base by L'.
Let us denote the reduction function by f
We have to prove:
for every (S1,...,Sl,k)
(S1,...,Sl,k) is in L
iff
f(S1,...,Sl,k)=(G,k') is in L'
This means two things that you missed
1. k' is not necessarily equal to k
2. You have to prove this only for values of k' that you get from the reduction.
What this means is that if you are given (S1,...,Sl,k) you have to prove:
If (S1,...,Sl,k) is in L (look at the definition of L) then (G,k') is in L'
If (G,k') is in L' (for the specific values of k' that you get from the reduction)then (S1,...,Sl,k) is in L.
The emphasis here is that you do not call Base with any k', but only with the values that the reduction creates.
Specifically for your technical problem, if k>L, the suggested solution in this thread is OK. since you know the answer is "false" for Set-Cover, you can give an instance of Base where the answer is "false", for example (G,0) is an option here. this means that k' will never be larger than L (here L is the number of sets of the input in set cover).
Re: Q2: polynomiality (is that even a word?) of the reduction אני רק רוצה לחזק את דברי שחר.
אתם יכולים לחשוב על זה בדיוק כמו ברדוקציות שראינו באוטומטים (למרות שלא אמרנו את זה). פונקצית הרדוקציה בודקת קודם כל (כמובן בזמן פולינומיאלי) האם הקלט לבעיה הראשונה הוא "חוקי", אם לא, יוצרת קלט "לא חוקי" עבור הבעיה השניה. אחרת ממשיכה כרגיל.
Re: Q2: polynomiality (is that even a word?) of the reduction I was actually trying to show that reduction f is a bijection, which would've proven that both problems are equivilent. But that's not the point at all, it's just much harder to do (or maybe impossible in this case).
Thanks!