Name
Abstract | ||
|---|---|---|
The comparator circuit model was originally introduced by Mayr et al. (1992) (and further studied by Cook et al. (2014)) to capture problems that are not known to be P-complete but still not known to admit efficient parallel algorithms. The class CC is the complexity class of problems many-one logspace reducible to the Comparator Circuit Value Problem and we know that NLOG⊆CC⊆P. Cook et al. (2014) showed that CC is also the class of languages decided by polynomial size comparator circuit families. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.ic.2018.02.002 | Information and Computation |
Keywords | Field | DocType |
Comparator circuits,Logspace computation,Polynomial size circuits | Complexity class,Discrete mathematics,Boolean circuit,Combinatorics,Distributive lattice,Comparator,Polynomial,Parallel algorithm,True quantified Boolean formula,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
261 | Part | 0890-5401 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Balagopal Komarath | 1 | 4 | 3.16 |
| Jayalal M. N. Sarma | 2 | 17 | 9.16 |
| K. S. Sunil | 3 | 1 | 1.04 |