The monotone circuit value problem with bounded genus is in NC
We present an efficient parallel algorithm for the general Monotone Circuit Value Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm generalizes a recent result by Limaye et al. who showed that MCVP with toroidal embedding (genus 1) is in NC when the input contains...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , , |
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | http://hdl.handle.net/10725/5416 http://dx.doi.org/10.1007/978-3-319-42634-1_8 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-42634-1_8 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | We present an efficient parallel algorithm for the general Monotone Circuit Value Problem (MCVP) with n gates and an underlying graph of bounded genus k. Our algorithm generalizes a recent result by Limaye et al. who showed that MCVP with toroidal embedding (genus 1) is in NC when the input contains a toroidal embedding of the circuit. In addition to extending this result from genus 1 to any bounded genus k, and unlike the work reported by Limaye et al., we do not require a precomputed embedding to be given. Most importantly, our results imply that given a P-complete problem, it is possible to find an algorithm that makes the problem fall into NC by fixing one or more parameters. Hence, we deduce the interesting analogy: Fixed Parameter Parallelizable (FPP) is with respect to P-complete what Fixed Parameter Tractable (FPT) is with respect to NP-complete. Similar work that uses treewidth as parameter was also presented by Elberfeld et al. in [6]. This work was partially supported by the German Research Foundation (DFG) within the Collaborative Research Center “On-The-Fly Computing” (SFB 901) and the International Graduate School “Dynamic Intelligent Systems”. |
|---|