Space-time isomorphism problem is intractable (NP-hard)

The problem of whether or not two different mathematical models of space-time describe the same space-time is not trivial. For example, the first spherically symmetric solution—the Schwarzschild metric—describes only part of the process of falling into a black hole, and other metrics were discovered for the same situation that also describe the subsequent events. These metrics turned out to be isomorphic in the sense that some 1-1 correspondence (coordinates transformations) transform one into another. But in the general case to find whether such an isomorphism exists is a difficult computational problem. There are some algorithms for smooth metrics, but the problem is also important for the nonsmooth metrics involving singularities. We prove that in the general case this isomorphism problem is intractable.     

Astrogeometry: Toward mathematical foundations

Inimage processing (e.g., inastronomy), the desired black-and-white image is, from the mathematical viewpoint, aset. Hence, to process images, we need to process sets. To define a generic set, we need infinitely many parameters; therefore, if we want to represent and process sets in the computer, we must restrict ourselves to finite-parameter families of sets that will be used to approximate the desired sets. The wrong choice of a family can lead to longer computations and worse approximation. Hence, it is desirable to find the family that it isthe best in some reasonable sense. In this paper, we show how the problems of choosing the optimal family of sets can be formalized and solved. As a result of the described general methodology, forastronomical images, we get exactly the geometric shapes that have been empirically used by astronomers and astrophysicists; thus, we have atheoretical explanation for these shapes.     

Unreasonable effectiveness of symmetry in physics

We prove that in some reasonable sense, every possible physical law can be reformulated in terms of symmetries. This result explains the well-known success of the group-theoretic approach in physics.     

Prediction problem in quantum mechanics is intractable (NP-Hard)

It is proved that both the prediction problem and the problem of reconstructing the state from the observations in quantum mechanics are NP-hard.     

Interval Arithmetic, Affine Arithmetic, Taylor Series Methods: Why, What Next?

In interval computations, the range of each intermediate result r is described by an interval r. To decrease excess interval width, we can keep some information on how r depends on the input x=(x ₁,...,x _n ). There are several successful methods of approximating this dependence; in these methods, the dependence is approximated by linear functions (affine arithmetic) or by general polynomials (Taylor series methods). Why linear functions and polynomials? What other classes can we try? These questions are answered in this paper.     

Approximately measured causality implies the Lorentz group: Alexandrov-Zeeman result made more realistic

If we know the causality relation between approximately known pairs of events, will we still be able to reconstruct affine coordinates? Our answer is: yes, we can reconstruct coordinates uniquely (modulo Lorentz group) from approximately measured coordinates. In this sense, we make the Alexandrov-Zeeman result more realistic.     

A new class of fuzzy implications. Axioms of fuzzy implication revisited

Many different fuzzy implication operators have been proposed; most of them fit into one of the two classes: implication operations that are based on an explicit representation of implication A → B in terms of &, , and ¬ (e.g., S-implications that are based on the formula B ¬ A), and R-implications that are based on an implicit representation of implication A → B as the weakest C for which C&B implies A. However, some fuzzy implication operations (such as b^a) cannot be naturally represented in this form. To describe such operations, we propose a new (third) class of implication operations called A-implications whose relation to &, , and ¬ is described by (implicit) axioms.     

Symmetry characterization of Pimenov's spacetime: A reformulation of causality axioms

In modern physics, many theories are formulated in terms of symmetries; therefore, if we want to incorporate, e.g., space-time physics into modern physics, it is desirable to reformulate space-time physical theories in terms of symmetries. In this paper, we provide such a reformulation for an axiomatic theory of kinematic causality.     

An Application of Logic to Combinatorial Geometry: How Many Tetrahedra are Equidecomposable with a Cube?

It is known (see Rapp [9]) that elementary geometry with the additional quantifier “there exist uncountably many” is decidable. We show that this decidability helps in solving the following problem from combinatorial geometry: does there exist an uncountable family of pairwise non-congruent tetrahedra that are n-equidecomposable with a cube? Mathematics Subject Classification: 03B25, 03C80, 51M04, 52B05, 52B10.