बहुपद समय का उपयोग कर "सबसे कठिन" समस्याएं क्या हैं?

Question

हाल ही में मैं a seminar work पढ़ कहते हैं जो:

मिलान एल्गोरिथ्म [सामान्य रेखांकन के लिए] भारित मामले, जो प्रतीत होता है करने के लिए बढ़ाया जा सकता है "सबसे मुश्किल" मिश्रित अनुकूलन समस्याओं कि हो सकता है में से एक हो बहुपद समय में हल हो गया।

तुरंत निम्नलिखित प्रश्न मेरे मन में आया था:

आप अन्य "पी मुश्किल" समस्याओं को जानते हैं?

अब के लिए मैं पी-हार्ड को परिभाषित करना चाहता हूं: "उस समस्या के लिए साहित्य में एक बहुपद एल्गोरिदम बहुत देर हो चुकी थी (1 9 50 के बाद)"। (या यदि कोई पहले से ही एक निर्धारिती एल्गोरिदम है जो बहुपद समय में समस्या हल करता है तो "हार्ड" को बेहतर तरीके से परिभाषित कैसे किया जा सकता है?)

Answer 1

वास्तव में "पी-पूर्ण" समस्याएं हैं, जिसका अर्थ है कि बहुपद समय में गणना की जा सकने वाली हर दूसरी समस्या को उन्हें कम किया जा सकता है। http://en.wikipedia.org/wiki/P-complete देखें।

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Answer 2

Primes is in P।

Answer 3

एक और "हार्ड" पी समस्या "रैखिक प्रोग्रामिंग" सुलझाने है।

Answer 4

The Assignment Problem जो हे में हल किया जा सकता (एन) को संशोधित किया Hungarian Algorithm द्वारा:

Answer 5

यदि आप नियमों को थोड़ा मोड़ना चाहते हैं, तो pseudo-polynomial time algorithms "बहुपद" है जिसे आप "बहुपद समय" में हल कर सकते हैं।

छद्म-बहुपद एल्गोरिदम का एक क्लासिक उदाहरण O(nW)knapsack problem पर गतिशील प्रोग्रामिंग समाधान है।