2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "traveling salesman algorithm" $\: \mapsto \:$ "traveling salesman problem" $\;\;\;$ ? $\hspace{1.98 in}$ $\endgroup$ – user6973 Jul 29 '15 at 11:54
  • $\begingroup$ 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. $\endgroup$ – Thomas Klimpel Jul 31 '15 at 5:55
  • $\begingroup$ Sorry for not answering earlier. Yes, I can confirm that is the calculi I refer. $\endgroup$ – MaiaVictor Aug 1 '15 at 9:50
  • $\begingroup$ I don't understand what the proposed edit changed. $\endgroup$ – MaiaVictor Aug 1 '15 at 9:51
  • 1
    $\begingroup$ It changed "algorithm" to "problem". $\;$ $\endgroup$ – user6973 Aug 2 '15 at 16:01
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ N!=NP $\mapsto$ P!=NP $\;$ $\endgroup$ – user6973 Jul 29 '15 at 11:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Jul 29 '15 at 14:05
  • $\begingroup$ @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". $\endgroup$ – Thomas Klimpel Jul 29 '15 at 14:31
  • $\begingroup$ 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. $\endgroup$ – Thomas Klimpel Jul 29 '15 at 23:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.