Circuit-size Lower Bounds and Non-reducibility to Sparse Sets
As remarked in Cook (1980), we do not know any nonlinear lower bound on the circuit-size of a language in P or even in NP. The best known lower bound seems to be due to Paul (1975). In this paper we show that first for each nonnegative integer k, there is a language Lk in Σ2∩π2 (of Meyer and Stockme...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149016 |
| _version_ | 1826208436949352448 |
|---|---|
| author | Kannan, Ravindran |
| author_facet | Kannan, Ravindran |
| author_sort | Kannan, Ravindran |
| collection | MIT |
| description | As remarked in Cook (1980), we do not know any nonlinear lower bound on the circuit-size of a language in P or even in NP. The best known lower bound seems to be due to Paul (1975). In this paper we show that first for each nonnegative integer k, there is a language Lk in Σ2∩π2 (of Meyer and Stockmeyer (1972) hierarchy) which does not have 0(n^k)-size circuits. Using the same techniques, one is able to prove several similar results. For example, we show that for each nonnegative integer k, there is a language Lk in NP that does not have 0(n^k)-size uniform circuits. This follows as a corollary of a stronger result shown in the paper. Finally, we note that existence of "small circuits" is in suitable contexts equivalent to being reducible to sparse sets. Using this, we are able to prove for example that for any time-constructible super-polynomial function f(n), NTIME(f(n)) contains a language which is not many-to-one p-time reducible to any sparse set. |
| first_indexed | 2024-09-23T14:05:25Z |
| id | mit-1721.1/149016 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T14:05:25Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490162023-03-30T03:30:57Z Circuit-size Lower Bounds and Non-reducibility to Sparse Sets Kannan, Ravindran As remarked in Cook (1980), we do not know any nonlinear lower bound on the circuit-size of a language in P or even in NP. The best known lower bound seems to be due to Paul (1975). In this paper we show that first for each nonnegative integer k, there is a language Lk in Σ2∩π2 (of Meyer and Stockmeyer (1972) hierarchy) which does not have 0(n^k)-size circuits. Using the same techniques, one is able to prove several similar results. For example, we show that for each nonnegative integer k, there is a language Lk in NP that does not have 0(n^k)-size uniform circuits. This follows as a corollary of a stronger result shown in the paper. Finally, we note that existence of "small circuits" is in suitable contexts equivalent to being reducible to sparse sets. Using this, we are able to prove for example that for any time-constructible super-polynomial function f(n), NTIME(f(n)) contains a language which is not many-to-one p-time reducible to any sparse set. 2023-03-29T14:19:55Z 2023-03-29T14:19:55Z 1981-10 https://hdl.handle.net/1721.1/149016 9157788 MIT-LCS-TM-205 application/pdf |
| spellingShingle | Kannan, Ravindran Circuit-size Lower Bounds and Non-reducibility to Sparse Sets |
| title | Circuit-size Lower Bounds and Non-reducibility to Sparse Sets |
| title_full | Circuit-size Lower Bounds and Non-reducibility to Sparse Sets |
| title_fullStr | Circuit-size Lower Bounds and Non-reducibility to Sparse Sets |
| title_full_unstemmed | Circuit-size Lower Bounds and Non-reducibility to Sparse Sets |
| title_short | Circuit-size Lower Bounds and Non-reducibility to Sparse Sets |
| title_sort | circuit size lower bounds and non reducibility to sparse sets |
| url | https://hdl.handle.net/1721.1/149016 |
| work_keys_str_mv | AT kannanravindran circuitsizelowerboundsandnonreducibilitytosparsesets |