  This paper argues that the requirement of applicableness of quantum linearity
to any physical level from molecules and atoms to the level of macroscopic
extensional world, which leads to a main foundational problem in quantum theory
referred to as the "measurement problem", actually has a computational
character: It implies that there is a generic algorithm, which guarantees exact
solutions to the Schrodinger equation for every physical system in a reasonable
amount of time regardless of how many constituent microscopic particles it
comprises. From the point of view of computational complexity theory, this
requirement is equivalent to the assumption that the computational complexity
classes P and NP are equal, which is widely believed to be very unlikely. As
demonstrated in the paper, accepting the different computational assumption
called the Exponential Time Hypothesis (that involves P!=NP) would justify the
separation between a microscopic quantum system and a macroscopic apparatus
(usually called the Heisenberg cut) since this hypothesis, if true, would imply
that deterministic quantum and classical descriptions are impossible to overlap
in order to obtain a rigorous derivation of complete properties of macroscopic
objects from their microstates.
