מחלקת NL.
16 views
Skip to first unread message
אריאל
Jul 2, 2009, 9:50:01 AM7/2/09
to Complexity Course, Spring 2009, Tel Aviv University
למה אם אפשר היה לנוע בסרט העד בNL לשני הצדדים המכונה הייתה NP?
Noam Schachter
Jul 2, 2009, 9:56:27 AM7/2/09
to Complexity Course, Spring 2009, Tel Aviv University
כי יכולת לתת הצבה ל-SAT, ולוודא אותה תוך שימוש במקום לוגריתמי.
החזרה אחורה מאפשרת לך לוודא שההשמה חוקית ומספקת.
יונית ונועם.
אריה שרון
Jul 2, 2009, 9:58:42 AM7/2/09
to complexity-course-spring...@googlegroups.com
כי אז אתה יכול להכריע את SAT
תקבל כעד הצבה מספקת
ואז בסרט העבודה תחזיק בכל פעם פסוקית אחת לפי הסדר
ועבור כל פסוקית אתה יכול לעבור קדימה ואחורה על סרט העד ולמצוא את ההצבה של המשתנים שמופיעים בה
אתה שומר בכל פעם רק פסוקית אחת ועוד קבועים ולכן מקום לוגריתמי
תקבל כעד הצבה מספקת
ואז בסרט העבודה תחזיק בכל פעם פסוקית אחת לפי הסדר
ועבור כל פסוקית אתה יכול לעבור קדימה ואחורה על סרט העד ולמצוא את ההצבה של המשתנים שמופיעים בה
אתה שומר בכל פעם רק פסוקית אחת ועוד קבועים ולכן מקום לוגריתמי
2009/7/2 אריאל <ariel...@gmail.com>
giladcoh
Jul 2, 2009, 10:24:12 AM7/2/09
to Complexity Course, Spring 2009, Tel Aviv University
בנוסף לכך שאתה יכול לפתור את SAT במכונה מהסוג הזה (מכונת NL שבה מותר
לחזור אחורה על סרט העד), חשוב להראות שהרדוקציות ל-SAT גם הן
לוגריתמיות,
ובאמת מתקיים שהרקוציה במשפט Cook-Levin היא לוגריתמית במקום.
לחזור אחורה על סרט העד), חשוב להראות שהרדוקציות ל-SAT גם הן
לוגריתמיות,
ובאמת מתקיים שהרקוציה במשפט Cook-Levin היא לוגריתמית במקום.
On 2 יולי, 16:58, אריה שרון <arish...@gmail.com> wrote:
> כי אז אתה יכול להכריע את SAT
> תקבל כעד הצבה מספקת
> ואז בסרט העבודה תחזיק בכל פעם פסוקית אחת לפי הסדר
> ועבור כל פסוקית אתה יכול לעבור קדימה ואחורה על סרט העד ולמצוא את ההצבה של
> המשתנים שמופיעים בה
> אתה שומר בכל פעם רק פסוקית אחת ועוד קבועים ולכן מקום לוגריתמי
>
> 2009/7/2 אריאל <arieleva...@gmail.com>
>
>
>
> > למה אם אפשר היה לנוע בסרט העד בNL לשני הצדדים המכונה הייתה NP?-הסתר טקסט מצוטט-
>
> -הראה טקסט מצוטט-
Reply all
Reply to author
Forward
0 new messages