Nexptime

NEXPTIME

NEXPTIME often arises in the context of interactive proof systems, where there are two major characterizations of it. The first is the MIP proof system, where we have two all-powerful provers which communicate with a randomized polynomial-time verifier (but not with each other). If the string is in the language, they must be able to convince the verifier of this with high probability. If the string is not in the language, they must not be able to collaboratively trick the verifier into accepting the string except with low probability. The fact that MIP proof systems can solve every problem in NEXPTIME is quite impressive when we consider that when only one prover is present, we can only recognize all of PSPACE; the verifier's ability to "cross-examine" the two provers gives it great power. See interactive proof system#MIP for more details.