Name
Abstract | ||
|---|---|---|
Based on the results of Blum, Shub and Smale [1], Meer [6], Cucker and Matamala [3] and Koiran [4], we develop the study of real computation models restricted to additive operations. More specifically we introduce some complexity classes defined by algebraic circuits and we study their relationships with the real computation model. We show that the languages accepted by nonuniform additive circuits of polynomial size and polylogarithmic depth are those accepted by uniform additive circuits of polynomial size and polylogarithmic depth with advice. Moreover, we prove that binary languages accepted by real uniform circuits of polynomial size and polylogarithmic depth, when the test nodes in the circuit are equality test, are the languages belonging to NC; when the test nodes are inequality test, the class obtained is NC/Poly. We also prove that the class defined by family of algebraic circuits with polynomial size and polylogarithmic depth is strictly contained in the class defined by real additive Turing machines working in polynomial time. |
Year | Venue | Keywords |
|---|---|---|
1994 | MFCS '94 Proceedings of the 19th International Symposium on Mathematical Foundations of Computer Science 1994 | nc-real complexity classes,additive circuits,polynomial time,complexity class,computer model,turing machine |
Field | DocType | ISBN |
PH,Complexity class,Discrete mathematics,Combinatorics,Structural complexity theory,Polynomial,P,UP,Real computation,Mathematics,PP | Conference | 3-540-58338-6 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michel Cosnard | 1 | 487 | 86.51 |
| Martín Matamala | 2 | 158 | 21.63 |