LCS Publication Details
Publication Title: TWO REMARKS ON THE POWER OF COUNTING
Publication Author: Papadimitriou, Christos H.
Additional Authors: Zachos, Stathis K.
LCS Document Number: MIT-LCS-TM-228
Publication Date: 8-1-1982
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
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 pf 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.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.