Two Remarks on the Power of Counting
The relationship between the polynomial hierarchy and Valiant's class #P is at present unknown. We show that some low portions of the polynomial hierarchy, namely deterministic polynomial algorithms using an NP oracle at most a logarithmic number of times, can be simulated by one #P computation...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149038 |
| _version_ | 1811083263467323392 |
|---|---|
| author | Papadimitriou, Christos H. Zachos, Stathis K. |
| author_facet | Papadimitriou, Christos H. Zachos, Stathis K. |
| author_sort | Papadimitriou, Christos H. |
| collection | MIT |
| description | The relationship between the polynomial hierarchy and Valiant's class #P is at present unknown. We show that some low portions of the polynomial hierarchy, namely deterministic polynomial algorithms using an NP oracle at most a logarithmic number of times, can be simulated by one #P computation. We also show that the class of problems solvable by polynomial-time nondeterministic Turing machines which accept whenever there is an odd number of accepting computations is idempotent, that is closed under usage of oracles from the same class. |
| first_indexed | 2024-09-23T12:30:22Z |
| id | mit-1721.1/149038 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T12:30:22Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490382023-03-30T03:45:16Z Two Remarks on the Power of Counting Papadimitriou, Christos H. Zachos, Stathis K. The relationship between the polynomial hierarchy and Valiant's class #P is at present unknown. We show that some low portions of the polynomial hierarchy, namely deterministic polynomial algorithms using an NP oracle at most a logarithmic number of times, can be simulated by one #P computation. We also show that the class of problems solvable by polynomial-time nondeterministic Turing machines which accept whenever there is an odd number of accepting computations is idempotent, that is closed under usage of oracles from the same class. 2023-03-29T14:21:54Z 2023-03-29T14:21:54Z 1982-08 https://hdl.handle.net/1721.1/149038 10733105 MIT-LCS-TM-228 application/pdf |
| spellingShingle | Papadimitriou, Christos H. Zachos, Stathis K. Two Remarks on the Power of Counting |
| title | Two Remarks on the Power of Counting |
| title_full | Two Remarks on the Power of Counting |
| title_fullStr | Two Remarks on the Power of Counting |
| title_full_unstemmed | Two Remarks on the Power of Counting |
| title_short | Two Remarks on the Power of Counting |
| title_sort | two remarks on the power of counting |
| url | https://hdl.handle.net/1721.1/149038 |
| work_keys_str_mv | AT papadimitriouchristosh tworemarksonthepowerofcounting AT zachosstathisk tworemarksonthepowerofcounting |