Could anyone confirm if for every algorithm running on some architecture M, there is an equivalent boolean function, and that the length of this boolean function is proportional to the runtime of the algorithm? Meaning that if A is a polynomial algorithm, then the corresponding boolean function f is also polynomial in length (has a polynomial number of boolean operations).
And wouldn't it be interesting if there was a computer program where we could plugin an algorithm and obtain the corresponding boolean function? The input variables of f would be the bits corresponding to the input to A... sounds possible?

12 Years
Discussion Span
Last Post by -Job-

It might depend:

What operations do you specifically mean by "boolean operations"?

Unless you have a wide-ranging definition of "boolean operations", the answer's no.


On second thought, your question makes no sense at all. What is a "polynomial algorithm"? Polynomial with respect to what? For example, factoring large numbers is a polynomial algorithm with respect to the value of the number you're trying to factor. For example, to factor n, you only need to check at most sqrt(n) numbers, using a naive algorithm. But measuring with respect to the length of n in digits, factoring does not run in polynomial time.

So, would your 'boolean function' be sqrt(n) large or exp(n) large?

Also, your question makes no sense because runtime is measured with respect to the size of the input. Your boolean function would have be a fixed length. And if it consists of 'boolean operations' then it would take the same amount of time to run, every time. Then could you give it any size input and have the algorithm run in constant time? No. For instance, a generic sorting algorithm cannot beat O(n log n) worst case, but your 'boolean function' would do just that, taking O(1) time no matter how many millions of items are in the input.

Does not sound possible.


I'm sorry, you're right it wouldn't be possible to describe a whole algorithm with a boolean function, but it is possible to describe a run of an algorithm on a specific input with a boolean function, and the size (number of of boolean operations by which i mean the logical OR, AND, NOT) of the function would be proportional to the time it took the run to complete.
Boolean algebra doesn't allow us to jump around in the function, hence the function would always take the same time to "execute". Of course, by adding jump statements, then we're just creating a programming language anyway. :P

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.