please look at the first question in this exercise (here's the solution) - there seems to be a polynomial algorithm to calculate the number of m length pathes in a graph. isn't it the same as HAM-PATH, if one sets m to be
אתה מתכוון לבעיית המסלול ההמילטוני? זה בכלל לא אותו דבר. אם תשים m כ| V |, זה לא אומר שבמסלולים שתקבל כל צומת מופיעה בדיוק פעם אחת (שזה מסלול המילטוני), אתה תקבל מספר מסלולים בהם יש | V | צמתים. אם הגרף שלך קשיר וללא מעגלים, אז כן, אבל בעיית המסלול ההמילטוני הג'נרית היא NPC.
anyway, if we're talking about complexity here's a sentences i have problem proving: P = NP -> NP = EXP as a matter of fact i kinda believe it's actually false, as i know how to prove P != EXP (regardless of P = / != NP) but that what the exam solution says...
