As Terence Tao has recalled several times, mathematics can benefit not only from correct proofs, or proofs that require some changes to be correct, but also from outlines of strategies for a proof, whether for opening lines of research or close them definitely. Here we discuss how a certain kind of logician could argue for P = NP following a translation between logics (TBL) approach. As P = NP amounts to FOL(LFPO) = SOL, one could argue for the latter by providing a suitable translation between those logics. Though here we do not provide such a translation, we explore which is the scope of a TBL approach applied to those logics as a strategy to argue for P = NP. Thus, our broad strategy is as follows:

1. Follow the identities provided by descriptive complexity theory (see [4]).
2. Compare the expressive powers of FOL(LFPO) and SOL via TBL (see [3] and [5]).
3. Discuss how the three known barriers in complexity theory (see [2]) represent constraints for the TBL approach in question to be acceptable.
4. Give reassurance for the TBL approach of three kinds with some examples: a) Philosophical: the corresponding translations does not imply any gratuitous counterintuitive claim regarding logic, mathematics or human nature. For example, an identification of FOL(LFPO) and SOL via logical translations does not imply any destruction of creativity or anything of that sort (cf. [1] and [6]). b) Conceptual: the translations does not distort the phenomena to be studied. For instance, the specific traits of NP problems are not necessarily lost when transferred to some version of FOL. c) Mathematical: the translations does not imply any obvious contradiction with well-established mathematical results. For example, we show that they are consistent with P ⊊ EXPTIME.

References

[1] Aaronson, S. (2016) P ≟ NP. In J. F. Nash Jr. and M. Th. Rassias (eds.). Open Problems in Mathematics. Springer: 1-121.

[2] Aaronson, S. & Wigderson, A. (2009). Algebrization: A New Barrier in Complexity Theory. ACM Transactions on Theory of Computing, 1(1): 1-54.

[3] Carnielli, W. A., M. E. Coniglio and I. M. L. D’Ottaviano (2009). New Dimensions on Translations Between Logics. Logica Universalis, 3(1): 1–18.

[4] Immerman, N. (1998). Descriptive Complexity. Springer-Verlag.

[5] Manzano, M. (1996). Extensions of First Order Logic. Cambridge University Press.

[6] Wigderson, A. (2006). P, NP and mathematics-a computational complexity perspective. In Proceedings of the International Congress of Mathematicians. EMS Publishing House: 665- 713.