Statements (51)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:contains |
NEXPTIME-complete problems
NEXPTIME-hard problems succinct version of many PSPACE-complete problems |
| gptkbp:definedIn |
the set of decision problems solvable by a nondeterministic Turing machine in exponential time
|
| gptkbp:formalDefinition |
NEXPTIME = ⋃_{k∈N} NTIME(2^{n^k})
|
| https://www.w3.org/2000/01/rdf-schema#label |
NEXPTIME
|
| gptkbp:introducedIn |
gptkb:complexity_theory
|
| gptkbp:numberOfIssues |
gptkb:succinct_circuit_satisfiability
succinct version of generalized scheduling problems succinct version of generalized resource allocation problems succinct version of generalized verification problems succinct version of generalized Geography succinct version of generalized Go succinct version of generalized Hex succinct version of generalized Othello succinct version of generalized Reversi succinct version of generalized Shogi succinct version of generalized TQBF succinct version of generalized abduction problems succinct version of generalized automata problems succinct version of generalized board games succinct version of generalized checkers succinct version of generalized chess succinct version of generalized decision problems succinct version of generalized deduction problems succinct version of generalized formula games succinct version of generalized graph problems succinct version of generalized inference problems succinct version of generalized learning problems succinct version of generalized logic games succinct version of generalized model checking succinct version of generalized planning problems succinct version of generalized puzzle games succinct version of generalized reasoning problems succinct version of generalized search problems succinct version of generalized synthesis problems succinct version of generalized tiling succinct version of generalized language recognition problems succinct version of generalized constraint satisfaction problems succinct version of generalized optimization problems succinct version of generalized reachability problems |
| gptkbp:openQuestion |
whether NEXPTIME = EXPTIME
whether NEXPTIME = NP whether NEXPTIME = PSPACE |
| gptkbp:relatedTo |
gptkb:EXPTIME
gptkb:PSPACE NP |
| gptkbp:standsFor |
nondeterministic exponential time
|
| gptkbp:bfsParent |
gptkb:EXPTIME
|
| gptkbp:bfsLayer |
5
|