האם זמן הפחתה פולינום?

2024 מְחַבֵּר: Fiona Howard | [email protected]. שונה לאחרונה: 2024-01-10 06:37

בתאוריית המורכבות החישובית, הפחתת זמן פולינומית היא שיטה לפתרון בעיה אחת באמצעות אחרת. הפחתות זמן פולינומיות משמשות לעתים קרובות בתורת המורכבות להגדרת הן מחלקות מורכבות והן בעיות שלמות עבור מחלקות אלו. …

מה נחשב זמן פולינום?

אלגוריתם אמור להיות בעל זמן פולינום אם זמן הריצה שלו מוגבל על ידי ביטוי פולינום בגודל הקלט עבור האלגוריתם, כלומר T(n)=O(n^k) עבור קבוע חיובי כלשהו.

איך אתה יודע אם משהו הוא זמן פולינום?

3 תשובות. אלגוריתם הוא פולינום (יש לו זמן ריצה פולינומי) אם עבור כמה k, C>0, זמן הריצה שלו בכניסות בגודל n הוא לכל היותר Cnk. באופן שווה, אלגוריתם הוא פולינום אם עבור כמה k>0, זמן הריצה שלו בכניסות בגודל n הוא O(nk).

מה קורה אם ההפחתה מותרת בזמן אקספוננציאלי?

אם ההפחתה מתאפשרת זמן אקספוננציאלי, אז זה יכול לפתור את הבעיה המקורית במלואה ולהפיק מופע טריוויאלי של בעיית היעד זה אומר שכל בעיה ב-NP ניתנת להפחתה לכל בעיה אחרת על ידי סוג כזה של הפחתות, אז כל בעיה ב-NP היא NP-שלמה עבור הפחתות זמן אקספוננציאליות.

מהו אלגוריתם מעריכי?

אלגוריתם אמור להיות זמן אקספוננציאלי, if T(n) הוא הגבול העליון על ידי 2^{poly( )} , כאשר poly(n) הוא פולינום כלשהו ב-n. באופן רשמי יותר, אלגוריתם הוא זמן אקספוננציאלי אם T(n) מוגבל על ידי O(2^{nk) עבור קבוע k. Ref:Wiki.}