Recent Forum Posts
From categories:
page 1123...next »

Computable does not mean polynomial.
The number of words $w \in \Sigma^*$ s.t. $w < f_L(i)$ is finite.

1. A language $L$ is trivial if $L=\Sigma^*$ or $L=\emptyset$
2. No

Yes, the updated version of the assignment was posted.
Thanks

You can use it only if you proved it in class.

Please see the common mistakes of HW4:

בשאלה 1: לא מיקמו את הראש הקורא מימין לפלט.

בשאלה 3: הרוב לא ציינו כלל את הכיוון הטריוויאלי (זה נכון שהוא פשוט אבל שקילות היא יחס דו כיווני)
בנוסף, לא דאגו לשאלה כיצד יודעים מאיפה להמשחך אחרי ההעתקה.
הטעות הגדולה ביותר שחזרה לא מעט פעמים בשאלה זו היא שימוש ב"הרבה סרטים" א) ללא הוכחת שקילות בין המודל החדש
למודל החדש מרובה סרטים.
ב) בלי הגדרה לכמות הסרטים, בפרט השתמשו בכמות סרטים ששווה למספר השינויים (עשוי להיות אינסופי).

בשאלה 4: נראה שהרבה מאוד סטודנטים לא הבינו את ההגדרה של shuffle.
והיו רבים שלא סיפקו הוכחת נכונות לבניה שלהם.

HW4 common mistakes by Dean DoronDean Doron, 24 Jun 2017 20:13

היי, האם ההנחה בתרגיל היא ש P!=NP ?
תודה

תרגיל בית 6 by Maya CahanaMaya Cahana, 24 Jun 2017 18:22

we learned in class that Rice's theorem gives us tools to determine if a language is in R or not. but actually it does more than that. if the empty set is not in C then from the proof itself we also know that it's not in Co-RE and if the empty set is in C then we know that L is not in RE. is this something we can use in the test to say if a language is in RE or not, or do we need to prove it before using?
thanks!

חלק מההגדרה של הפונקציה הוא כזה
|f(x)| = |x|-1
האם הכוונה ל"קטן שווה"?

תרגיל בית 6 שאלה 3 by kolac0kolac0, 24 Jun 2017 16:01

בכיתה ראינו את המשפט:
A language L is decidable iff there exist an enumerator that enumerate it in lexicographic order.

אבל בתרגול הוכחנו שזה נכון רק לשפות אינוספיות

אז זה נכון לכל שפה בR או רק לשפות אינסופיות?

1. מה נחשבת לשפה "טריוויאלית" בP/ NPC? אפשר לקבל דוגמה?
2. שאלה קצת טיפשית, אבל יכול להיות שהכוונה בשאלה היא "קיימות שתי שפות לא טריוויאליות A,B…"?
בעיקר בסעיף b
תודה רבה

בתשובה בונים מונה ואומרים שהוא פונקציה חשיבה.
האם "חשיבה" בהקשר של מונים אומר פולינומיאלית?
ובכל מקרה - איך מוכיחים שהפונקציה הזו חשיבה?
יכול להיות שנצטרך לעבור על אינסוף מילים לא מקבלות לפני שנגיע למילה ה-i שמקבלת

למה אנחנו צריכים לסמן גם את הצד הימני? האם זה בכדי לאפשר _ גם בקלט?

No

Re: EX5 Q2 by Yuval MoskovitchYuval Moskovitch, 23 Jun 2017 06:41
EX5 Q2
yonatan vaineryonatan vainer 22 Jun 2017 18:07
in discussion Discussions / Q&A Spring 2017 » EX5 Q2

Can I assume that useless state is a state other then q.accept and q.reject ?

EX5 Q2 by yonatan vaineryonatan vainer, 22 Jun 2017 18:07

A polynomial verifier runs in polynomial time in $|x|$

Re: Verifier by Yuval MoskovitchYuval Moskovitch, 22 Jun 2017 07:04
Verifier
IlorIlor 21 Jun 2017 07:47
in discussion Discussions / Q&A Spring 2017 » Verifier

The verifier runs at polynomial time depending on x only? No matter how long c is?

Verifier by IlorIlor, 21 Jun 2017 07:47

We count all the cells used by $M'$.

Re: Ex05Q4b by Yuval MoskovitchYuval Moskovitch, 21 Jun 2017 07:28
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License