Implicit Simulation of FNC Algorithms
Daniel Sawitzki · 2007
Implicit algorithms work on their input’s characteristic functions and should solve problems heuristically by as few and as efficient functional operations as possible. Together with an appropriate data structure to represent the characteristic functions they yield heuristics which are successfully applied in numerous areas. It is known that implicit algorithms which execute t(N) functional operations while using at most k log 2 N Boolean variables can be simulated by CREW-PRAMs with O(N k) processors and parallel runtime O((t(N)) 2). In this paper we consider the opposite case and present a simulation of FNC algorithms by implicit OBDD-based algorithms with polylog(N) functional operations and O(log N) Boolean variables.