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?
-Job- 0 Newbie Poster
Rashakil Fol 978 Super Senior Demiposter Team Colleague
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.
Rashakil Fol 978 Super Senior Demiposter Team Colleague
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.
-Job- 0 Newbie Poster
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
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.