-
آرشیو :
نسخه زمستان 1396
-
موضوع :
سایر شاخه های علوم رایانه
-
نویسنده/گان :
بهنوش داریوشی ، مرتضی زلف پور آرخلو
-
چکیده :
درسالهای اخیر استراتژیهای جدیدی برای حل مسائل دشوار ابداع شدهاست که باالهام از سایر رویدادهای فیزیکی وبیولوژیکی بدنبال یافتن پاسخ مسائل دشوار می باشند، مسائلی که پیچیدگی زمانی یافتن راه حل آنها بطور نمایی با اندازه ی مساله متناسب می باشند. دراین مقاله، ابتدا به ارائه تعریف سادهای ازطبقه بندی مسائل (دشوار،ساده) میپردازیم. البته کلاسهای پیچیدگی بسیار زیادی وجود دارند که در اینجا قصد بررسی آنها وجود ندارد. نشان خواهیم داد که در گروه وسیعی از مسائل دشوار، یافتن پاسخ برای مساله متناظر با یافتن می نیمم مطلق یک تابع است. تابعی که به خاطر وفور تعداد می نیمم های موضعی امکان یافتن می نیمم مطلق در آن دشوار است. سپس به بررسی استراتژی منبعث از فیزیک برای حل این مساله می پردازیم و در این راه از کوششهای اخیر برای حل این مساله با استفاده از تعبیر فیزیکی از دگردیسی فضای حالت با افزایش چگالی قیود بهره می جوییم
-
کلید واژه :
مسائل دشوار، مسائل رام، NP-complete، ارضاپذیری فرمول K-SAT، Hamiltonian، همبستگی، تغییر فاز، رفتار آستانه ای.
-
Title :
Physically Inspired Method for Solving Interactable Problems
-
مراجع :
[1] S. Arora and B. Boaz, “Computational Complexity: A Modern Approach”, Cambridge University Press, 2009.
[2] J. Hromkovic, “Theoretical Computer Science, Springer, 2010.
[3] G. Chaitin, “Thinking about Godel and Turing: Esays on Complexity”, Word Scientific, 2007.
[4] J. Hromkovic, “Algorithms for Hard Problems: Introduction to Combinatorial Optimization, Randomization, Approximation and Heuristics”, Springer, 2004.
[5] A. Percus, G. Istrate, C. Moore(Editors), “Computational Complexity and Statistical Physics”, Oxford University Press, 2006.
[6] R. Marino, G. Prisi, F. Ricci-Tersenghi, “The Backtracking Survey Propagation Algorithm for Solving Random K-SAT Problems”, Nature Communication, Vol. 7, 12996, 2016.
[7] S. Kirkpatrick, B. Selman, “Critical Behavior in The Satisfiability of Random Boolean Expression”, Science, Vol. 264, pp. 1297-1301, 1994.
[8] R. Monasson, R. Zecchina, S. Krikpatrick, B. Selman, L. Troyansky, “Determining Computational Complexity from Characteristic Phase transitions”, Nature, Vol. 400, pp. 133-137, 1999.
[9] M. Mezard, A. Montanari, “Information, Physics and Computation”, Oxford University Press, 2009.
[10] J. Ding, A. Sly, N. Sun, “Proof of The Satisfiability Conjecture for Large K”, Proceedings of the Forty-Seventh Annual ACM on Symposium on The Theory of Computing, USA, 2015.
[11] S. Mertens, M. Mezard, R. Zecchina, “Threshold Values of Random K-SAT from the Cavity Method”, Random structures and Algorithms, Vol. 28, pp. 340-373, 2006.
[12] A. Montanari, F. Ricci-Tersenghi, G. Semerjian, “Clusters of Solutions and Replica Symmetry Breaking in Random K-Satisfiability”, Journal of Statistical Mechanics, pp. 04004, 2008.
[13] D. Achlioptas, F. Ricci-Tersenghi, “On The Solution-Space geometry of Random Constraint satisfaction Problems”, Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, Seattle, 2006.
[14] J.H. Zhao, H.J. Zhou, “Statistical Physics of Hard Combinatorial Optimization: Vertex Cover Problem”, Chinese Physics B, Vol. 23, N. 7, 2014.
[15] L. Zdeborova, “Statistical Physics of Hard Optimization Problems”, Phd thesis, Charles University of Prague, 2008.
- صفحات : 109-117
-
دانلود فایل
( 507 KB )