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)))))

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?

  • 5
    $\begingroup$ 1. It depends on how you encode the problem. 2. This looks more like SAT solver code golf. $\endgroup$ – Huck Bennett Aug 11 '15 at 15:05
  • 1
    $\begingroup$ The simplest one I know of is $\mu$-recursive: $\mu_x \mu_y (ax^2 + by = c)$. $\endgroup$ – Kaveh Aug 13 '15 at 2:43
  • $\begingroup$ @Kaveh Sorry, could you elaborate? What is that? $\endgroup$ – MaiaVictor Aug 13 '15 at 3:57
  • $\begingroup$ @HuckBennett 1. So what? 2. So what? - read your comment as: "we don't like the problem." $\endgroup$ – MaiaVictor Aug 13 '15 at 3:58
  • 1
    $\begingroup$ 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. $\endgroup$ – 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).

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

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.