# 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

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