Statements (23)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
theoretical computer science
|
| gptkbp:contains |
gptkb:PSPACE
gptkb:EXP NP NEXPTIME-complete problems |
| gptkbp:definedIn |
languages decidable by a nondeterministic Turing machine in exponential time
|
| gptkbp:example |
succinct version of QBF
succinct version of SAT |
| gptkbp:formalDefinition |
NEXP = ⋃_{k∈N} NTIME(2^{n^k})
|
| gptkbp:hasSubgroup |
ELEMENTARY
|
| https://www.w3.org/2000/01/rdf-schema#label |
NEXP
|
| gptkbp:numberOfIssues |
succinct QBF
succinct circuit SAT |
| gptkbp:openProblem |
NEXP vs EXP
NEXP vs NP NEXP vs PSPACE |
| gptkbp:relatedTo |
gptkb:EXPTIME
gptkb:PSPACE gptkb:EXP NP |
| gptkbp:standsFor |
nondeterministic exponential time
|
| gptkbp:bfsParent |
gptkb:P/poly
|
| gptkbp:bfsLayer |
6
|