<p>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.</p>

<p>From the information you give in the question, I conclude that LAL is P-time hard. The article <a href="http://www.sciencedirect.com/science/article/pii/S0890540108001119" rel="nofollow"><em>Light types for polynomial time computation in lambda calculus</em> by R. Baillot and K. Terui</a> confirms this, by showing that DLAL (dual light affine logic) is a <a href="https://en.wikipedia.org/wiki/P-complete" rel="nofollow">P-complete</a> subset of LAL.</p>

<hr>

<p>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.</p>

CC BY-SA 3.0
2015-07-29T14:05:49.600Z
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.
Sasho Nikolov
CC BY-SA 3.0
2015-07-29T14:31:27.567Z
@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".
Thomas Klimpel
CC BY-SA 3.0
2015-07-29T23:54:28.873Z
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.
Thomas Klimpel
CC BY-SA 3.0
2015-07-29T09:00:57.323Z
2015-07-29T09:00:57.323Z
Thomas Klimpel
<p>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?</p>

CC BY-SA 3.0
2015-07-31T05:55:54.697Z
Can you please confirm that the article [*Light types for polynomial time computation in lambda calculus* by R. Baillot and K. Terui](http://www.sciencedirect.com/science/article/pii/S0890540108001119) 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.
Thomas Klimpel
CC BY-SA 3.0
2015-08-01T09:50:00.870Z
Sorry for not answering earlier. Yes, I can confirm that is the calculi I refer.
MaiaVictor
CC BY-SA 3.0
2015-08-01T09:51:10.527Z
I don't understand what the proposed edit changed.
MaiaVictor
<cc.complexity-theory><lo.logic><lambda-calculus>
Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?
MaiaVictor
# Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?

(Asked by: username_0 on 2015-07-29)

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?

**Tags:** cc.complexity-theory, lo.logic, lambda-calculus
> **Comments:**
> **username_1**: Can you please confirm that the article [*Light types for polynomial time computation in lambda calculus* by R. Baillot and K. Terui](http://www.sciencedirect.com/science/article/pii/S0890540108001119) 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.  
> **username_0**: Sorry for not answering earlier. Yes, I can confirm that is the calculi I refer.  
> **username_0**: I don't understand what the proposed edit changed.  

---

## 1 answers

### Answer by username_1 on 2015-07-29. Score: 1

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](http://www.sciencedirect.com/science/article/pii/S0890540108001119) confirms this, by showing that DLAL (dual light affine logic) is a [P-complete](https://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: @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".  
> **username_1**: 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.  

---

