Can the hamiltonian cycle problem be solved in ploynomial time?

في حال تحقق الشرط وكان لدينا hamiltonian cycle فإنها تستهلك زمن p(n) لأننا سنقوم فقط بتنفيذ الخوارزمية  A على البيان مرة واحدة ،اما في حال الشرط غير محقق فإننا سنقوم بالمرور على كل وصلات البيان والتي عددها m ،من أجل كل وصلة سنقوم بتنفيذ الخوارزمية A على البيان المتبقي وذلك بتكلفة قدرها P(n) وبالتالي زمن التنفيذ الكلي بأسوأ حالة هو , m.P(n) وهو زمن كثير الحدود

أن الخوارزمية A المستخدمة لإيجاد Hamiltonian Cycle  هي:

Algorithm A:

Input: an undirected graph G=(V,E)

Output: HC in G  if Sol(G) != Ø

if C(G) =0 then

Output "no HC in G"

else

For each edge e in E do

If C(G\{e}) = 1 then

G <--G\{e}

output (G)