卷 16, 编号 2 (2025)
theoretical computer science
Complexity of Computations with Time Travel
摘要
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 LOGSPACEThe 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.
Program Systems: Theory and Applications. 2025;16(2):3-54
3-54
hardware and software for distributed and supercomputer systems
Features of the organization of an unified scientific and technological space
摘要
An unified scientific and technological space can provide a common platform for more effective interaction of the scientific community in the implementation of complex scientific and technical projects, search for and attraction of necessary resources to various scientific research and projects. In connection with the current transnational tasks of our time in the field of science and education, these can be, for example, the spaces of Russia, the Union State, the Arctic zone, neighboring countries, etc. This paper describes the requirements and provides proposals for the construction of the main components of the unified scientific-technological space in the form of automatic workstations for analysts and information portals. Much attention is paid to the conceptual model of the information portal and its architecture is given. The article touches upon important issues in the field of standardization of the components of the unified scientific-technological space.
Program Systems: Theory and Applications. 2025;16(2):55-79
55-79
High-speed associative interaction of distributed digital objects operating under uncertainty
摘要
Associative operations and algorithms utilizing them are considered for high-speed network data processing and management in distributed digital systems with unpredictable actions of system objects, unknown time and location of result appearance within the system, system failures, and unexpected external environment influences. These operations and algorithms enabled the creation of interaction methods (based on qualitative features without using object addresses and data) and distributed associative operations involving a group of objects simultaneously in each operation. The execution of these operations does not increase data transmission time. To accelerate the system's response to unexpected influences, three types of adaptive connection structures with different reaction speeds to external effects are proposed. All connections are restructured simultaneously.
Program Systems: Theory and Applications. 2025;16(2):81-109
81-109
artificial intelligence, intelligence systems, neural networks
Improving the accuracy of segmentation masks using a generative-adversarial network model
摘要
Masks obtained using the deep learning model Mask R-CNN may in some cases contain fragmented contours, uneven boundaries, false fusions of adjacent objects, and areas with missed segmentation. The more detection objects in the image and the smaller their size, the more often various types of defects in their masks are encountered. Examples of such images include aerial photographs of cottage and garden associations and cooperatives characterized by high building density. To correct these defects, it is proposed to use a generative adversarial network model that performs post-processing of the predicted Mask R-CNN masks.A qualitative assessment of the model formed in the work demonstrated that it is capable of restoring the integrity of contours at an acceptable level, filling in missing areas, and separating erroneously merged objects. Quantitative analysis using the IoU, precision, recall, and F1-score metrics showed a statistically significant improvement in the segmentation quality compared to the original Mask R-CNN masks. The obtained results confirmed that the proposed approach allows to increase the accuracy of the formation of object masks to a level that satisfies the requirements of their practical application in automated aerial photograph analysis systems.
Program Systems: Theory and Applications. 2025;16(2):111-152
111-152