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
Recommended Answers
Jump to PostIt 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.
All 3 Replies
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
-Job-
0
Newbie Poster
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.