Physical Portrayal of Computational Complexity
المؤلف
المصدر
ISRN Computational Mathematics
العدد
المجلد 2012، العدد 2012 (31 ديسمبر/كانون الأول 2012)، ص ص. 1-15، 15ص.
الناشر
Hindawi Publishing Corporation
تاريخ النشر
2012-03-05
دولة النشر
مصر
عدد الصفحات
15
التخصصات الرئيسية
الملخص EN
Computational complexity is examined using the principle of increasing entropy.
To consider computation as a physical process from an initial instance to the final acceptance is motivated because information requires physical representations and because many natural processes complete in nondeterministic polynomial time (NP).
The irreversible process with three or more degrees of freedom is found intractable when, in terms of physics, flows of energy are inseparable from their driving forces.
In computational terms, when solving a problem in the class NP, decisions among alternatives will affect subsequently available sets of decisions.
Thus the state space of a nondeterministic finite automaton is evolving due to the computation itself, hence it cannot be efficiently contracted using a deterministic finite automaton.
Conversely when solving problems in the class P, the set of states does not depend on computational history, hence it can be efficiently contracted to the accepting state by a deterministic sequence of dissipative transformations.
Thus it is concluded that the state set of class P is inherently smaller than the state set of class NP.
Since the computational time needed to contract a given set is proportional to dissipation, the computational complexity class P is a proper (strict) subset of NP.
نمط استشهاد جمعية علماء النفس الأمريكية (APA)
Annila, Arto. 2012. Physical Portrayal of Computational Complexity. ISRN Computational Mathematics،Vol. 2012, no. 2012, pp.1-15.
https://search.emarefa.net/detail/BIM-463356
نمط استشهاد الجمعية الأمريكية للغات الحديثة (MLA)
Annila, Arto. Physical Portrayal of Computational Complexity. ISRN Computational Mathematics No. 2012 (2012), pp.1-15.
https://search.emarefa.net/detail/BIM-463356
نمط استشهاد الجمعية الطبية الأمريكية (AMA)
Annila, Arto. Physical Portrayal of Computational Complexity. ISRN Computational Mathematics. 2012. Vol. 2012, no. 2012, pp.1-15.
https://search.emarefa.net/detail/BIM-463356
نوع البيانات
مقالات
لغة النص
الإنجليزية
الملاحظات
Includes bibliographical references
رقم السجل
BIM-463356
قاعدة معامل التأثير والاستشهادات المرجعية العربي "ارسيف Arcif"
أضخم قاعدة بيانات عربية للاستشهادات المرجعية للمجلات العلمية المحكمة الصادرة في العالم العربي
تقوم هذه الخدمة بالتحقق من التشابه أو الانتحال في الأبحاث والمقالات العلمية والأطروحات الجامعية والكتب والأبحاث باللغة العربية، وتحديد درجة التشابه أو أصالة الأعمال البحثية وحماية ملكيتها الفكرية. تعرف اكثر