Publication Details:
Լույս է տեսնում 1966 թվականից՝ տարին 4 անգամ։
Journal or Publication Title:
ՀՀ ԳԱԱ Տեղեկագիր: Ֆիզիկա = Proceedings of the NAS RA: Physics
Date of publication:
Volume:
Number:
ISSN:
Official URL:
Additional Information:
Stepanyan V. A., Khachatryan S. G., Hovhannisyan S. A.
Title:
Термодинамика физических приближений недетерминистических полиномных полных задач
Other title:
Thermodynamics Of Physical Approximations To Non Deterministic Polynomial Complete Problems
Creator:
Степанян, В. А. ; Хачатрян, С. Г. ; Оганисян, С. А.
Corporate Creators:
Американский Университет Армении
Contributor(s):
Պատ․ խմբ․՝ Գ․ Մ․ Ղարիբյան (1966-1992) ; Գլխ․ խմբ․՝ Վ․ Մ․ Հարությունյան (1993-2021) ; Կ․ Մ․ Ղամբարյան (2022-)
Subject:
Coverage:
Abstract:
Недетерминистические полиномные полные задачи играют важную роль в современной коммуникации, безопасности и многих других областях. Одной из наиболее известных НП-полных задач является задача составления экзаменационного расписания. В задаче дана информация о предметах и о студентах, которые записались на некоторые из них, а также временные интервалы зарезервированные для экзаменов по этим предметам. Необходимо найти такое расписание, при котором ни у одного из студентов не будет одновременно зарезервировано несколько экзаменов. Мы моделируем эту НП-полную задачу как одномерную систему частиц. Добавив некоторые взаимодействия между частицами на основе данных задачи, мы решаем уравнения движения до достижения системой равновесия. Затем, мы используем состояние равновесия, чтобы собрать частицы вместе так, чтобы каждый кластер представлял собой один временной интервал. Чтобы рассмотреть физику этой модели, мы используем метод реплик, с целью найти функционал свободной энергии в этой системе. Формулируется гипотеза, что все или, по крайней мере, большинство численных методов возможно описать в рамках этой модели с помощью соответствующего выбора взаимодействия между частицами.
Non Deterministic Polynomial Complete problems are playing an essential role in nowadays communications, security and many other fields. One of the well-known NP-complete problems is the Examination Timetabling problem. Given the information about the courses and the students that have taken some of those courses as well as the time slots for the exams of those courses the problem asks if there is a timetable such that no student has two exams simultaneously. We are modeling this NP-complete problem as a system of particles with one dimensional motion. After adding some interactions between the particles based on the problem we are simulating the motion and arriving to an equilibrium. We then use the equilibrium state to group the particles together where each cluster represents a time slot. To discuss the physics of this model we use the Replica method to find the free energy functional of this system. A hypothesis is formulated that all or at least most numerical solutions for NP-complete problems can be brought to this model with some configuration of interactions between the particles.
Type:
Format:
Identifier:
doi:10.54503/0002-3035-2022-57.1-52