Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR07-028 | 12th February 2007 00:00

Implicit Simulation of FNC Algorithms

RSS-Feed




TR07-028
Authors: Daniel Sawitzki
Publication: 22nd March 2007 12:06
Downloads: 3411
Keywords: 


Abstract:

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 $\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.



ISSN 1433-8092 | Imprint