Analysis on the computability over the efficient utilization problem of the four-dimensional space-time

Research paper by Wenqi Huang, Kun He

Indexed on: 20 Jul '11Published on: 20 Jul '11Published in: Computer Science - Computational Complexity


This paper formally proposes a problem about the efficient utilization of the four dimensional space-time. Given a cuboid container, a finite number of rigid cuboid items, and the time length that each item should be continuous baked in the container, the problem asks to arrange the starting time for each item being placed into the container and to arrange the position and orientation for each item at each instant during its continuous baking period such that the total time length the container be utilized is as short as possible. Here all side dimensions of the container and of the items are positive real numbers arbitrarily given. Differs from the classical packing problems, the position and orientation of each item in the container could be changed over time. Therefore, according to above mathematical model, the four-dimensional space-time can be utilized more truly and more fully. This paper then proves that there exists an exact algorithm that could solve the problem by finite operations, so we say this problem is weak computable. Based on the understanding of this computability proof, it is expected to design effective approximate algorithms in the near future. A piggyback work completed is a strict proof on the weak computability over general and natural case of the three-dimensional cuboid packing decision problem that all parameters are positive real numbers.