मैं जानना चाहता हूं कि क्या एक सन्निकटन योजना जो पूरी तरह से बहुपद-समय सन्निकटन योजना है - क्या यह एक बहुपद-समय सन्निकटन योजना भी है?

2 3

क्या यह एक बहुपद-समय सन्निकटन योजना भी है? धन्यवाद!

यहां दो प्रासंगिक समस्याएं हैं (सही या गलत):

  1. किसी भी निश्चित ϵ>0 के लिए O(n​2/ϵ) में चलने वाली एक सन्निकटन योजना पूरी तरह से बहुपद-समय सन्निकटन योजना है।
  2. किसी भी निश्चित ϵ>0 के लिए O(n2(1/ε)3) में चलने वाली एक सन्निकटन योजना एक बहुपद-समय सन्निकटन योजना है।
1
Feng Hang 24 मई 2018, 05:49

1 उत्तर

सबसे बढ़िया उत्तर

दिलचस्प सवाल के लिए धन्यवाद। मैंने थोड़ा शोध किया और इसके साथ आया बहुत पीटीएएस (बहुपद-समय सन्निकटन योजना) और पूरी तरह से पीटीएएस पर अच्छा अकादमिक व्याख्यान।

जैसा कि व्याख्यान में कहा गया है:

एल्गोरिथ्म का चलने का समय n में बहुपद होना चाहिए; हालांकि पर इसकी निर्भरता घातीय हो सकती है। तो चलने का समय O((2 ^ (1/ε)) * n^2) हो सकता है उदाहरण के लिए, या O(n ^ (1/ε)), या O((n ^ 2)/ε), आदि अगर पैरामीटर 1/ε पर निर्भरता भी बहुपद है तो हम पूरी तरह से बहुपद-समय सन्निकटन योजना (एफपीटीएएस) की बात करते हैं। इस लेक्चर में हम FPTAS का उदाहरण देते हैं।

चूंकि पीटीएएस में से मांग एक घातीय निर्भरता की है, तो स्पष्ट एफपीटीएएस पीटीएएस का उप-मामला है, क्योंकि 1/ε बहुपद निर्भरता (ओ (एफपीटीएएस) <ओ (पीटीएएस)) का है।

निचला रेखा - एफपीटीएएस पीटीएएस है।

0
Rann Lifshitz 24 मई 2018, 06:08