What would $\mathcal{P} \neq \mathcal{NP}$ tell us about some non-constructive proofs?

Question

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 method to 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}$ and TSP is $\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$ (YES or NO)?

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}$?

Answer 1

I think that such a non-constructive method for solving an NP-complete problem can always be transformed into a polynomial-time constructive method by re-running the non-constructive method on a sequence of modified versions of the original problem. It's a little more straightforward in the case of Satisfiability (i.e.: given a boolean formula, does there exist a satisfying assignment). Suppose you have a boolean formula such that your non-constructive method returns TRUE (i.e.: there exists a satisfying assignment). Fix the first variable, $x_1$, to TRUE in the original formula and re-run the non-constructive method on this new formula. If the non-constructive method still returns TRUE, then we know we have a satisfying assignment in the original formula with $x_1 = $TRUE, otherwise we set $x_1 = $ FALSE. Repeat on the remaining variables and you'll have your answer.

A similar trick can be applied to TSP by setting the distances of all but one edge out of each node to some value $>L$.

Edited to add:

I think I should also be explicit here. If we are able to treat this non-constructive proof as a black box that can be executed in polynomial time, then we can use it to construct explicit solutions to NP-complete problems in polynomial time. So, if we assume that P $\neq$ NP, this implies that such a hypothetical non-constructive proof cannot be "run" (for whatever that might mean) in polynomial time. In the example given at the bottom of the question, this would imply that the calculation of the numbers $x_i(W)$ and/or the function $f(x_1, \ldots, x_m, L)$ should not be calculable in polynomial time. Otherwise, we would just use the above trick and explicitly construct a satisfying TSP tour in polynomial time.

Answer 2

I think you may need to formulate your question more precisely.

Consider the following "nonconstructive proof": If you do blah-blah-blah and the result is 1 then YES, but if the result is 0 then NO, where "blah-blah-blah," upon closer inspection, amounts to running a Turing machine that exhaustively tries all possible permutations, and outputs 1 if it finds a suitable permutation, but outputs 0 if it does not.

This "proof" is pretty short since the Turing machine is rather simple. Secretly, of course, it "constructs" the permutation, but it keeps that information private and does not output it, so from the outside it looks nonconstructive.

If this sort of thing counts as a "nonconstructive proof" then we don't need to wait for someone to resolve the P ≠ NP question. We have the proof today.

If you don't want this sort of thing to count then you need to specify carefully what you do and do not allow.

I conjecture that you may be interested in proof complexity, which is related to but different from computational complexity. But this is just a conjecture.

Answer 3

I suspect that one learns nothing about such proofs, even in the case that P equals NP. (If a specific polynomial time algorithm were given for 3-SAT, we could build one for any NP problem, of course, and we would then learn something. But you are not asking about that situation.) Let me illustrate with a particular problem (which turns out to be in P, and is easily but not trivially so demonstrated), and at the same time show that the problem representation is important.

The input is a finite tuple of integers $k_i$, each greater than 1, which represents a hypercubic graph with number of vertices the product of the $k_i$, and is a "brick-shaped" subset with the edge lengths given by the $k_i$ of the infinite hypercubic lattice graph given by the product of the integers with itself. The output is Yes if there is a Hamiltonian cycle (a TSP) in this brick and No if not.

Take a moment if you wish to find a poly-time algorithm for this problem. It turns out the base used to encode the input affects the time needed to solve the problem.

Suppose the input is represented in tertiary base. Here is a sketch of an algorithm to solve the problem. For each input integer given in base 3, take its residue modulo two. If for one of the integers the result is 0, output Yes and stop. Otherwise process all the integers, find their residues as equal to 1, and then output No and stop.

As an exercise, show that a base two encoding of the input can permit a quicker algorithm , especially if the hardware supports it.

It turns out the problem specification on the specified input domain is equivalent to the following: return Yes if the input tuple contains an even integer, otherwise return No. Note that you do not always have to examine all of the input, and with a base two encoding, you just have to examine the least significant bit of the $k_i$'s until you find a zero.

Until you analyze the problem, this seems almost like magic: you examine a (often proper) subset of the input quickly and come up with an answer. This is because you understand the pattern of Yes instances so well that you can distinguish them from No instances quickly, but may not be able to explain why unless you educate the reader about the technique of modular arithmetic (and the reason why this matters; I also leave that as an exercise).

If I tell you that there is such a pattern for every input instance of (a polynomial time encoded version of) 3-SAT, and then you test me and I give you correct Yes/ No answers on your battery of examples in time much less than it took you to verify them yourself, you might believe me. If you ask for the pattern, and I say that in order to describe it we have to start with simplicial homology and apply some recent results of Peter Scholze and Caucher Birkar, you might be determined and attempt to understand the complicated description, but if you are like me and a lot of other people, you might give up and still declare it a mystery.

In short the mere fact of whether P and NP differ will not tell us anything (besides existence) about constructive or non constructive proofs. There are many complicated and obscure patterns out there, and P = NP would just tell us about asymptotics, but not whether it was brief to describe and capable of being understood after (say) a year of concentrated study.

Gerhard "Work On Simplifying CFSG Instead" Paseman, 2018.08.29.

Answer 4

I think the important distinction that may illuminate your question is between a proof that a particular instance $(W,L)$ belongs to the language TSP, and a proof that a particular algorithm for TSP is correct.

Consider the nondeterministic-Turing-machine $A$ that guesses a path $\pi$ and returns true if the length is at most $L$, returning false if all guesses fail. We can easily prove this is a correct nondeterministic algorithm for TSP. The proof is a finite fixed-size object.

Now consider a particular instance $(W,L)$. If we have a path $\pi$ whose distance is less than $L$, we can regard $\pi$ as a "proof" that the instance is in the TSP language. In fact, we can have a deterministic polynomial-time Turing Machine to check this proof's correctness: it simulates $A$ on the guess $\pi$ and outputs true if $A$ does. This "proof" $\pi$ will have a length that grows with the size of $(W,L)$.

This seems very important to your question because, again, for a given algorithm there is just a fixed finite-length proof it is correct (for all input sizes), while we can interpret nondeterministic TMs as guessing-and-checking a "proof" that a given instance is in the language.

---

If I interpret correctly, your question supposes we have a theorem that characterizes an NP-hard language such as TSP, e.g.:

Theorem. A string $s = (W,L)$ is a valid TSP instance if and only if $f(W,L) = 0$.

or perhaps "...if there exists a $\pi$ such that $f(W,L,\pi) = 0$."

We can interpret such theorems as a theorem that a certain algorithm correctly decides TSP, e.g.

Alg. Given $(W,L)$, return yes if $f(W,L) = 0$ and no otherwise.

The proof of this is some finite-sized string, and I don't expect the asymptotic statement $P \neq NP$ will tell us much about that proof. But it would imply this algorithm does not run in polynomial time. So we learn about the computational complexity of checking the theorem's conditions, but seemingly not about the theorem's proof.

---

Now, you might have asked about algorithms that are "nonconstructive" in the sense that they answer whether an instance is in the language, but they don't come with a "proof" $\pi$ of membership. We saw that nondeterministic Turing machines can be interpreted as coming with proofs that an instance is in a language. But I could have some e.g. exponential-time algorithm that checks an instance and outputs yes or no, but it doesn't really come with any short proof that the instance is in the language.

I don't know that $P \neq NP$ can say much about such algorithms, but you can think about more nuanced statements. For example, if we show that $NEXP \neq NP$, then there are problems that have exponential-length proofs of membership, but not polynomial-length ones. If we show $PSPACE \supsetneq NP$, then some PSPACE-hard problem like if a chess position is winning does not generally have short proofs. Etc.