Lane A. Hemaspaandra, Ashish Naik, Mitsunori Ogihara, Alan L. Selman

Is there an NP function that, when given a satisfiable formula

as input, outputs one satisfying assignment uniquely? That is, can a

nondeterministic function cull just one satisfying assignment from a

possibly exponentially large collection of assignments? We show that if

there is such a nondeterministic function, then the polynomial ...
more >>>

Stephen A. Fenner

We show that the counting classes AWPP and APP [Li 1993] are more robust

than previously thought. Our results identify asufficient condition for

a language to be low for PP, and we show that this condition is at least

as weak as other previously studied criteria. Our results imply that

more >>>

Vikraman Arvind, Piyush Kurur

We show that Graph Isomorphism is in the complexity class

SPP, and hence it is in $\ParityP$ (in fact, it is in $\ModkP$ for

each $k\geq 2$). We derive this result as a corollary of a more

general result: we show that a {\em generic problem} $\FINDGROUP$ has

an $\FP^{\SPP}$ ...
more >>>