Much has been written about the class UP see related (even more in literature) example question here. Much is understood about the class UP, and its place in collapsing the PH too. UP has a played a part in understanding randomized reductions, too. The class (birefly) UE on the other hand is the class of problems recognized by an unambiguous nondeterministic TM running in exponential time with a linear exponent. The Complexity Zoo reference briefly mentions its relation to E, as UP is to P.

Many-one reducibilities in this regime could mean that the reductions run in exponential time. A natural question that arises about UE under these reductions is that if E = UE, does NEXP have sparse languages that are NEXP-hard?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.