[-] שאלה כללית ברדוקציות
by tzviya - Monday, 25 June 2012 18:32:00
אם אני בונה רדוקציה על סמך רדוקציה אחרת בצורה הבאה:

g(x)= (f(x) , w)

האם בכיוון ההוכחה:
g(x) in L1-> x in l2

ניתן להניח ש
g(x)

הוא מהצורה המסוימת
(f(x) , w)

(כלומר שהאיבר הראשון שלו הוא הפעלה של
f
על אותו האיקס?)



thread
Re: שאלה כללית ברדוקציות
by taig - Tuesday, 26 June 2012 00:33:03
Please reformulate, I don't understand the question.
Generally, if the reduction from L1 to L2 is f(x) = x' then on the proof direction: x' \in L2 --> f(x) in L1 then x' is the output of your reduction and not some general string.
thread