Asymmetry in Diagrams of Stable Marriage Problems: Stable Manifolds Mapped from Stable Matchings

摘要

If the measure of computational complexity, defined as the computation time required to solve a problem, is independent from the computer used, the measure reflects the complexity of the algorithm and the problem instance. If the measure further does not depend on the algorithm, it purely reflects the complexity of the problem instance. Focusing on the stable marriage problem, we propose a mapping from problem instances to dynamical systems. The computational time required for a dynamical system to reach equilibrium is used to measure the complexity. A diagram similar to a phase diagram of dynamical systems is proposed to indicate the structure of stable manifolds of dynamical systems. Based on computer simulations, we conjecture that the diagram is qualitatively invariant to the mapping and naturally reflects the complexity of the problem instance. The diagram indicates not only that the stable equilibrium corresponds to the stable matchings but also that the contour structure corresponds to the discrete structure of the lattice formed by the stable matchings.