שיחה:FNP – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
תגית: אות סופית באמצע מילה |
|||
שורה 9:
==גרסת ה-FNP של שפה שהיא NP שלמה==
לא אמר שמום מקום הביטוי "פונקציה NP-שלמה. נאמר כי גרסת ה-FNP של שפה שהיא NP-שלמה היא בעיה NP-קשה. הכנסת לפחות טעות אחת בהגדרת .BPP, כך שמוטב קצת צניעות. [[משתמש:בשלני|בשלני]] - [[שיחת משתמש:בשלני|שיחה]] 02:04, 9 באוקטובר 2016 (IDT)
:שמח שבחרת לדון על כך, אז ככה כשאומרים על בעיה שהיא NP קשה, מדברים על כך שקיימת רדוקציית התאמה ניתנת לחישוב בזמן פולינומי(מכונה בקיצור ״רדוקציית קארפ״ על שמו של ריצ׳ארד קארפ המפורסם) ממופע של ״בעיה״ A למופע של ״בעיה״ B, כך שהקלט המקורי שייך לשפה A אםם הקלט החדש שייך לשפה B, המונח ״בעיה״ הוא טרמינולוגיה לא טובה, זה מושג שלא נהוג להשתמש בו, עובדה שהתבלבלת כאן. [[מיוחד:תרומות/79.181.65.119|79.181.65.119]] 02:10, 9 באוקטובר 2016 (IDT)
| |||