# Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?

An answer to the traveling salesman (and similar) problems can be easily verified on light lambda-calculi. Also, if I understand correctly, the light lambda-calculi can compute every polinomial-time computable function. That way, if one can prove that the traveling salesman problem can't be encoded on the light lambda-calculi, that would also prove the problem can't be solved in poly-time, which would also prove P!=NP. Is that correct, or am I confusing some concepts?

• "traveling salesman algorithm" $\: \mapsto \:$ "traveling salesman problem" $\;\;\;$ ? $\hspace{1.98 in}$
– user6973
Commented Jul 29, 2015 at 11:54
• Can you please confirm that the article Light types for polynomial time computation in lambda calculus by R. Baillot and K. Terui refers to the same LAL or light lambda calculi as your question. Alternatively, you may also provide a better reference. Based on the comment by Sasho Nikolov, the details of the reduction will be important for answering the question, i.e. which type of encoding you would have to rule out for proving P!=NP. Commented Jul 31, 2015 at 5:55
• Sorry for not answering earlier. Yes, I can confirm that is the calculi I refer. Commented Aug 1, 2015 at 9:50
• I don't understand what the proposed edit changed. Commented Aug 1, 2015 at 9:51
• It changed "algorithm" to "problem". $\;$
– user6973
Commented Aug 2, 2015 at 16:01

Yes, in the same sense that if you prove that a specific NP-complete problem can't be reduced to a specific P-hard problem, then you also prove P!=NP. The only issue is that the reduction for which P-hardness hold must be "compatible" with the allowed encodings.

From the information you give in the question, I conclude that LAL is P-time hard. The article Light types for polynomial time computation in lambda calculus by R. Baillot and K. Terui confirms this, by showing that DLAL (dual light affine logic) is a P-complete subset of LAL.

My own experience is that many P-complete problems look attractive and natural. My favorites are linear programming and Horn-satisfiability, but I guess that DLAL (or LAL) look even more attractive to you. But even so they are attractive, using them for resolving N!=NP is probably futile. More than one reduction of specific NP-complete problems to linear programming has been published, but the reductions turned out to exponentially increase the size of the problem.

• N!=NP $\mapsto$ P!=NP $\;$
– user6973
Commented Jul 29, 2015 at 11:55
• People keep making this mistake: P-hard and P-complete problems are totally irrelevant to P vs NP. They are useful for L vs P or NC vs P. In fact P $\neq$ NP if and only if there exists an NP-hard problem which is not polytime reducible to the language $\{0, 1\}$ (or any non-trivial language). The latter is of course not P-hard unless L=P. Commented Jul 29, 2015 at 14:05
• @SashoNikolov You are right, my answer makes this mistake. However, I will need some time to see that P-complete problems are really totally irrelevant to P vs NP. Also, just because my answer is wrong in its current form doesn't mean that the answer to the question by Viclib is "No". Commented Jul 29, 2015 at 14:31
• Even so my answer makes the mistake pointed out be Sasho Nikolov, I'm no longer sure whether it is really wrong. The remark "The only issue is that the reduction for which P-hardness hold must be "compatible" with the allowed encodings." might actually prevent it from going wrong, if interpreted correctly. Of course, this should be worked out in more detail, to really answer the question by Viclib. Commented Jul 29, 2015 at 23:54