Consider the related problems of, given a strongly normalizing lambda term, computing the longest and shortest paths ending in a normal form.

In terms of bits of input the optimal complexity is some uncomputable function (since the input can be a Busy Beaver etc.). But the complexity of brute force is still quite large even in terms of the result, is there a faster algorithm than bfs/computing the whole graph?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.