# What is the simplest known solver for a np-complete problem?

Lets define the simpler of two terms as the one with shortest description length on the untyped λ-calculus. Trying to find the simplest solver for a np-complete problem, I've got this:

solve_sat = (λab.(a(λcde.(c(λf.(d(λgh.(g(λij.j)(fgh)))))
(c(λf.(d(λgh.(g(λij.i)(fgh)))))e)))(λcd.(c(λef.f)d))
(λcd.(c(λefg.(f(ge)))(λe.e)b(c(λefg.(f(ge)))(λe.e)b)
d))(λcd.d)))


This λ-term takes 2 arguments, a church number telling the arity of a church-encoded boolean formula, and the formula itself, and returns "true" if it is satisfiable. Of course, this term is quite long, but serves as an upper ceiling. My question is: what is the shortest known term that solves an NP-complete problem?

• 1. It depends on how you encode the problem. 2. This looks more like SAT solver code golf. – Huck Bennett Aug 11 '15 at 15:05
• The simplest one I know of is $\mu$-recursive: $\mu_x \mu_y (ax^2 + by = c)$. – Kaveh Aug 13 '15 at 2:43
• @Kaveh Sorry, could you elaborate? What is that? – MaiaVictor Aug 13 '15 at 3:57
• @HuckBennett 1. So what? 2. So what? - read your comment as: "we don't like the problem." – MaiaVictor Aug 13 '15 at 3:58
• 1. I agree with Huck Bennett that this seems more suitable for Code Golf unless you explain why this is of interest as a theoretical computer science question. 2. Quadratic Diophantine equation problem is NP-complete. My program is not in lambda calculus but in $\mu$-recursion. – Kaveh Aug 13 '15 at 5:26

I believe that the problem as you've described it is undecidable. Given that UTMs are Turing-equivalent to the lambda calculus, we can rephrase your question as follows:

 Describe the shortest Turing machine that completely decides any NP-complete problem.


Assume that we have a fixed UTM and indexing of Turing machines. Then suppose that you have, in fact, found the true "shortest Turing machine" that decides an NP-complete problem. The issue is that there may be a shorter Turing machine that fails to halt on all inputs. This shorter Turing machine cannot be found algorithmically to not decide an NP-complete problem, due to the undecidability of the halting problem.

So, as a general statement, we can say the following: Given as input a class of problems X, there is no Turing machine that finds the shortest Turing machine that decides any member of X.

This is somewhat related to Kolmogorov complexity; see, in particular, the proof that Kolmogorov complexity is undecidable (it uses the Berry paradox).

• I didn't ask for the shortest, I ask for the shortest known... – MaiaVictor Aug 13 '15 at 3:57