A simple physics-motivated equivalent reformulation of P=NP that makes this equality (slightly) more plausible
Jaime Nava, Vladik Kreinovich
In our opinion, one of the reasons why the problem P=NP is so difficult is that while there are good intuitive arguments in favor of PĖ¸=NP, there is a lack of intuitive arguments in favor of P=NP. In this paper, we provide such an argument â based on the fact that in physics, many dependencies are scale-invariant, their expression does not change if we simply change the unit in which we measure the corresponding input quantity (e. g., replace meters by centimeters). It is reasonable to imagine similar behavior for time complexity tA(n) of algorithms A: the form of this dependence does not change if we change the unit in which we measure the input length (e. g., from bits to bytes). One can then easily prove that the existence of such scale-invariant algorithms for solving, e. g., propositional satisfiability is equivalent to P=NP. This equivalent reformulation of the formula P=NP is, in our opinion, much more intuitively reasonable than the original formulation â at least to those who are familiar with the importance of scale-invariance in physics.
CYBERNETICS AND PHYSICS, Vol. 1, No. 4, 2012 , 274â278.