Prev: Crankfest!
Next: Rule-based integration
From: Sadeq on 9 Jun 2010 07:53
Hi there!

The polynomial-time hierarchy (PH) is simply defined in a recursive
manner.

For example, for all k>=0, the \Sigma_{k+1} complexity class is
defined as NP^\Sigma_k.

My question is, whether on can write \Sigma_{k+1} as \Sigma_k^NP ?

This is somehow counterintuitive, but I saw a variation of it in the
following paper:

Vikraman Arvinda, Johannes Köblerb, Uwe Schöningb, Rainer Schuler, "If
NP has polynomial-size circuits, then MA = AM" Theoretical Computer
Science, 1995.
 | 
Pages: 1
Prev: Crankfest!
Next: Rule-based integration