Count and Tree in Uniform NC(1)

Based on the function algebras of $AC\sp0$ and $NC\sp1$ (in (9)), we prove the following results: (1) count is in uniform $NC\sp1.$ (2) The equivalence of tree and k-BRN. (3) Multiple addition is in uniform $TC\sp0.$ (4) tree is uniform $NC\sp1$ complete under $AC\sp0$ reduction. We also discuss weak multiple product which is computable in uniform $TC\sp0.$ All proofs here are function algebraic.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Lee, Jui-Lin

Contributors dc:contributor

• Takeuti, Gaisi

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI9717298

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/86941