Four polynomial-time hierarchies on functions are introduced, which are considered to be generalizations of Valiant’s counting function class #P, class Span-P introduced by Kobler et al., Krentel’s optimization func...Four polynomial-time hierarchies on functions are introduced, which are considered to be generalizations of Valiant’s counting function class #P, class Span-P introduced by Kobler et al., Krentel’s optimization function class Opt-P, and F2p. It is shown that our polynomial hierarchies of optimization functions are the same as that defined by Krentel. The relationships within every hierarchy and between them are studied.展开更多
文摘Four polynomial-time hierarchies on functions are introduced, which are considered to be generalizations of Valiant’s counting function class #P, class Span-P introduced by Kobler et al., Krentel’s optimization function class Opt-P, and F2p. It is shown that our polynomial hierarchies of optimization functions are the same as that defined by Krentel. The relationships within every hierarchy and between them are studied.
