3 ms·
Are all polynomial time algorithms implementable with primitive recursion? You would need to know the constant factor, right?
by reuben364 3y ago
Are all polynomial time algorithms implementable with primitive recursion? You would need to know the constant factor, right?
- adastra22 3y agoIn practice, yes. And for real world applications I know of, the depth of primitive recursion is small enough that loops can be fully unrolled. So e.g. bitcoin’s lack of a looping construct isn’t even a problem.