אם יש רדוקצייה פולינומיאלית מבעיה A לבעייה B אז אם B ב-NP גם A ב-NP. לא ראינו הוכחה של זה ולא לגמרי ברור לי איזה מוודא צריך לקחת ל-A? הרי צריך לשים לב שהמוודא יהיה פולינומיאלי בגודל הקלט (שב-A). אם הרדוקצייה היא פונקצייה f לא אוכל לקחת מוודא שמשתמש בה כי אז יהיה פולינומיאלי ב-f(x) ולא ב-x. אז איזה מוודא לוקחים?
Date: 08 Jun 2011 10:51
Number of posts: 9
RSS: New posts
not clear. I'll write it in english:
if there is a polynomial reduction from A to B then if B is in NP, A is also in NP.
Which verifier is taken in order to prove that A is in NP?
I.e. Polynomial in f(x) (which is itself polynomial of x) is a polynomial of x.
Proof: Composition of two polynomials is itself polynomial: b(ax^n)^m = b * a^m * x^(m+n) which is c*x^p (therefore polynomial) where p=m+n and c=b*a^m.
Though we never talked about how f affects the "witness", clearly we need some kind of transforamtion which gets a witness for A and returns a witness for B (on which the verifier runs in polynomial time).
I'm not sure how your idea solves the question.
If your proof uses verifiers then you do indeed need such a transformation. But why go to the trouble, the proof is much simpler:
We assume A <=p B and want to prove that B in NP ==> A in NP.
Since B in NP there is a TM that decides B in NP (i.e. polynomial time). We'll call it M.
We build a TM that will decide A in NP as follows:
Given an input x we invoke the reduction f (which exists since we assumed A <=p B), and on the result, f(x) we invoke M.
The machine's output (accept/reject) is simply the output of M(f(x)).
By the definition of a reduction x in A <==> f(x) in B <==> M accepts f(x) <==> The machine described above accepts.
Therefore the machine's language is indeed A.
The fact that it's in NP is due to what my previous post.
Since the runtime is the runtime of M on f(x), which is polynomial, and f(x) is polynomial in |x|, the total runtime is polynomial in x.
If you want to prove this with verifiers, then I'm not sure how you would deal with the witnesses.
Turing, please note that you just claimed to solve the biggest open question in CS:
"Since B in NP there is a TM that decides B in NP (i.e. polynomial time). We'll call it M."
NP is not (yet) polynomial.
I guess you meant there is a TM that verifies B in polynomial time or s.th like that.
And one more question to Ori:
it might occuer that problems A and B are in completely different "worlds"- meaning on is in graphs and one is in Set theory and same applys for the witnesses. Don't we need to prove that the transfomation of a witness for A to an equivilent witness for B is polynomial as well?
Deﬁnition: NP is the set of languages decidable in polynomial time on non-deterministic TMs.
Since B in NP it is a language decidable in polynomial time on a non-deterministic TM. We'll call that machine M.
I claimed no more than was defined in the lectures.
It doesn't matter. To verify that x is in A, we use the verifier of B on f(x).
The witness that x is in A, would actually be a witness for f(x) in B.
x is in A iff there exists such witness.
Think of SAT<p Clique.
To verify SAT, we construct a graph using the reduction, and the witness gives us a clique in that graph.