What algorithm solves high-order unification for untyped terms in most cases? High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation a =&gt; b, where a and b are terms on the simply typed lambda calculus, a containing free variables, finds a substitution S such that aS =&gt; b, where =&gt; stands for "has the same beta normal form" (up to variable renaming). For example, given the following problem:

a = (λt . t 
    (F (λ f x . (f (f (f x))))) 
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))


One can come with the solution:

 F = (λ a b c . (a b (a b c)))


Since that substitution makes a = b hold. My question is: what's an efficient (i.e., polytime) algorithm that solves this problem for as many cases as possible?
Maybe you should try nominal unification. In the paper nominal unification, it gives 4 examples which are untyped $\lambda$-terms.