ECCC-Report TR07-028https://eccc.weizmann.ac.il/report/2007/028Comments and Revisions published for TR07-028en-usThu, 22 Mar 2007 12:06:17 +0200
Paper TR07-028
| Implicit Simulation of FNC Algorithms |
Daniel Sawitzki
https://eccc.weizmann.ac.il/report/2007/028Implicit 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 $\BO(N^{k})$ processors and parallel runtime $\BO((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 $\BO(\log N)$ Boolean variables.
Thu, 22 Mar 2007 12:06:17 +0200https://eccc.weizmann.ac.il/report/2007/028