Details

Autor(en) / Beteiligte

• Papadimitriou, Christos H.
• Zachos, Stathis K.

Titel

Two remarks on the power of counting

Ist Teil von

• Theoretical Computer Science, 2005, p.269-275

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2005

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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.