New non-uniform lower bounds for uniform classes

Fortnow, L; Santhanam, R

Conference item

New non-uniform lower bounds for uniform classes

Abstract:: We strengthen the nondeterministic hierarchy theorem for non-deterministic polynomial time to show that the lower bound holds against sub-linear advice. More formally, we show that for any constants d and d' such that 1 <= d < d', and for any time-constructible bound t=o(n^d), there is a language in NTIME(n^d) which is not in NTIME(t)/n^{1/d'}. The best known earlier separation of Fortnow, Santhanam and Trevisan could only handle o(log(n)) bits of advice in the lower bound, and was not tight with respect to the time bounds. We generalize our hierarchy theorem to work for other syntactic complexity measures between polynomial time and polynomial space, including alternating polynomial time with any fixed number of alternations. We also use our technique to derive an almost-everywhere hierarchy theorem for non-deterministic classes which use a sub-linear amount of non-determinism, i.e., the lower bound holds on all but finitely many input lengths rather than just on infinitely many. As one application of our main result, we derive a new lower bound for NP against NP-uniform non-deterministic circuits of size O(n^k) for any fixed k. This result is a significant strengthening of a result of Kannan, which states that not all of NP can be solved with P-uniform circuits of size O(n^k) for any fixed k. As another application, we show strong non-uniform lower bounds for the complexity class RE of languages decidable in randomized linear exponential time with one sided error.

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Fortnow, L., & Santhanam, R. (2016). New non-uniform lower bounds for uniform classes. 31st Conference on Computational Complexity (CCC 2016), 19:1–19:14.

MLA Style

Fortnow, L, and R Santhanam. “New Non-Uniform Lower Bounds for Uniform Classes.” 31st Conference on Computational Complexity (CCC 2016), Leibniz International Proceedings in Informatics, 2016, pp. 19:1–19:14.

Chicago Style

Fortnow, L, and R Santhanam. 2016. “New Non-Uniform Lower Bounds for Uniform Classes.” In 31st Conference on Computational Complexity (CCC 2016), 19:1–19:14. Leibniz International Proceedings in Informatics. Schloss Dagstuhl.
Print