Теоретические основания программных систем. Рубрика в журнале - Программные системы: теория и приложения

Complexity of Computations with Time Travel

Milad Joudakizadeh, Anatoly P. Beltiukov

Статья научная

This paper explores a mathematical model of computation that can be interpreted as a computer capable of receiving data from future states of its own computational process. Under certain combinations of input data and programs, such computations may become infeasible due to emerging contradictions or lead to ambiguous outcomes. We investigate programs for which this process is always feasible and yields a unique result. It is demonstrated that, in the absence of computational complexity constraints, such machines can output the value of any recursively decidable predicate within a fixed time after the computation begins—referred to as the response delay time—while the computation process must continue even after the result is produced. When the total runtime of these machines is bounded by a polynomial function of the input size, they precisely recognize languages belonging to the intersection of the NP and co-NP complexity classes, with the same constant response delay time in the aforementioned sense. Possible practical implementations of such a computer are examined, including an analysis of operational protocols leveraging quantum annealing to select the appropriate computational process. It is shown that, with parallelization of the computational process, the class of problems solvable by these machines in polynomial time corresponds to the PSPACE complexity class. Additionally, a mode of operation is studied in which these machines have direct access to input data. In this case, if the runtime is limited to a logarithmic function of the input size, the class of problems solvable by such a parallelized computer encompasses LOGSPACE The findings of this study can be applied to develop new programming principles for nondeterministic computational machines, where data transmission from the future is employed instead of nondeterministic choices.

Бесплатно

Построение расписания при решении задачи поиска в Desktop Grid

Ивашко Е.Е., Чернов И.А.

Статья научная

В статье рассмотрена математическая модель решения в Desktop Grid задачи поиска — перебора некоторого пространства дискретных объектов в поисках единственного, удовлетворяющего заданным условиям. На основе ранее полученных математических результатов представлена оптимальная стратегия поиска для случаев однородных и неоднородных по вычислительной сложности самих заданий и их повторных проверок; предложен новый метод построения расписания при решении задачи поиска в Desktop Grid. Важным практическим результатом при этом является механизм динамической репликации, обеспечивающий высокую доступную производительность. Приведены результаты численного моделирования, демонстрирующие преимущества предложенного расписания.

Бесплатно

Проверка бисимуляционной эквивалентности формальных моделей игровых механик с охранными условиями и взвешенными переходами

Кугуракова В.В.

Статья научная

Настоящая статья посвящена задаче формальной проверки эквивалентности двух реализаций одной игровой механики. На практике эта задача возникает при рефакторинге игровой логики, сравнении независимых реализаций одной спецификации и верификации балансировочных преобразований. Для формального представления таких механик используется модель GD-FST (Game Design Finite State Transducer). Стандартный подход теории верификации — бисимуляция — здесь неприменим напрямую, поскольку в GD-FST рёбра несут не просто метки, а пары (условие охраны, вес), что порождает новую нетривиальную задачу согласования переходов. Вклад работы: (1) введено определение бисимуляционной эквивалентности для трансдьюсеров GD-FST, учитывающее структуру рёбер формализма; (2) предложен алгоритм проверки бисимуляционной эквивалентности, построенный на адаптации классического разбиения Канеллакиса–Смолки; (3) доказаны корректность и полнота алгоритма. Практическая значимость результата состоит в возможности автоматической проверки того, что рефакторинг или балансировочное преобразование игровой механики не изменяет её наблюдаемого поведения. Полученный аппарат применим не только к игровым механикам, но и к другим системам, управляемым правилами с охранными условиями и числовыми весами.

Бесплатно