|
In computational complexity theory, the complexity class NEXPTIME (sometimes called NEXP) is the set of decision problems that can be solved by a non-deterministic Turing machine using time 2''n'' O(1) and unlimited space. In terms of NTIME, : Alternatively, NEXPTIME can be defined using deterministic Turing machines as verifiers. A language ''L'' is in NEXPTIME if and only if there exist polynomials ''p'' and ''q'', and a deterministic Turing machine ''M'', such that * For all ''x'' and ''y'', the machine ''M'' runs in time 2''p(|x|)'' on input ''(x,y)'' * For all ''x'' in ''L'', there exists a string ''y'' of length 2''q(|x|)'' such that ''M(x,y)'' = 1 * For all ''x'' not in ''L'' and all strings ''y'' of length 2''q(|x|)'', ''M(x,y)'' = 0 We know :P NP EXPTIME NEXPTIME and also, by the time hierarchy theorem, that : NP NEXPTIME If P = NP, then NEXPTIME = EXPTIME (padding argument); more precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P.〔Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. ''Information and Control'', volume 65, issue 2/3, pp.158–181. 1985. (At ACM Digital Library )〕 == Alternative characterizations == 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. Another interactive proof system characterizing NEXPTIME is a certain class of probabilistically checkable proofs. Recall that NP can be seen as the class of problems where an all-powerful prover gives a purported proof that a string is in the language, and a deterministic polynomial-time machine verifies that it is a valid proof. We make two changes to this setup: * Add randomness, the ability to flip coins, to the verifier machine. * Instead of simply giving the purported proof to the verifier on a tape, give it random access to the proof. The verifier can specify an index into the proof string and receive the corresponding bit. Since the verifier can write an index of polynomial length, it can potentially index into an exponentially long proof string. These two extensions together greatly extend the proof system's power, enabling it to recognize all languages in NEXPTIME. The class is called PCP(poly, poly). What more, in this characterization the verifier may be limited to read only a constant number of bits, i.e. NEXPTIME = PCP(poly, 1). See probabilistically checkable proofs for more details. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「NEXPTIME」の詳細全文を読む スポンサード リンク
|