Let me sum up my - hopefully correct - understanding of the travelling salesman problem and complexity classes. It's about decision problems:

"[...] a decision problem is a problem that can be posed as a yes-no question of the input values. Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an

effective methodto determine the existence of some object."

The travelling salesman problem (**TSP**) - as a decision problem - is to find an answer to the question:

Given an $n \times n$ matrix $W = (w_{ij})$ with $w_{ij} \in \mathbb{Q}$ and a number $L\in \mathbb{Q}$.

Is there a permutation $\pi$ of $\{1,\dots, n\}$ such that

$$L(\pi) = \sum_{i=1}^{n} w_{\pi(i)\pi(i+1)} < L?$$

_{with modular addition, i.e. $n+1 = 1$}

The answer can be given as a specific example (the output of a constructive "problem solver") which then can be checked for correctness. For **TSP** we know that a specific example given by a constructive problem solver (e.g. a specific permutation $\pi$) can be checked in polynomial time for $L(\pi) < L$, that means **TSP** $\in\mathcal{NP}$.

But the answer may also be given by just a boolean value **YES** or **NO** , which cannot be checked at all. (What would we try to check?)

The first kind of answer is given by algorithms that are programmed to read arbitary matrices $W$ and numbers $L$ and give an example $\pi$. These are equivalent to constructive proofs which somehow construct a $\pi$ from given $W$ and $L$, and which may be correct or not.

The second kind of answer is given by non-construtive proofs - which nevertheless give an answer. Such a proof also "reads" some general $W$ and $L$ and makes some general considerations about them, e.g. like this: If numbers $x_1, \dots x_n$ can be calculated from $W$ and they relate to $L$ such that $f(x_1,\dots, x_n, L) = 0$ then the answer is **YES** otherwise **NO**.

My question is:

If some day it is proved that

TSP$\not\in \mathcal{P}$ (because $\mathcal{P} \neq \mathcal{NP}$ andTSPis $\mathcal{NP}$-hard), what do we learn about hypothetical non-construtive proofs that for given $W$ and $L$ there exist solutions $\pi$ with $L(\pi) < L$ (YESorNO)?

Or is the talk about such proofs only a chimera - because they are ill-defined or cannot exist for obvious reasons?

**Remark 1:** Since proofs have no run-time, the things we can learn about them may concern only their length and/or complexity (in general: structure).

**Remark 2:** Very short and simple algorithms may have exponential run-times.

To think more specifically about this: Assume there is a proof that proves:

If you calculate numbers $x_1(W),\dots, x_m(W)$ of a quadratic matrix $W$ and you find that if $f(x_1,\dots,x_m,L) = 0$ then there is a permutation $\pi$ with $L(\pi) < L$.

What could be said about this (hypothetical!) proof, assuming that $\mathcal{P} \neq \mathcal{NP}$?