Relativizations comparing NP and exponential time
From MaRDI portal
Recommendations
Cited in
(32)- Some hierarchies of relativized time-bounded complexity classes
- Simplicity, immunity, relativizations and nondeterminism
- Almost every set in exponential time is P-bi-immune
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
- The coincidence of the classes of problems solvable by deterministic algorithms bounded by exponential time and polynomial space
- scientific article; zbMATH DE number 4130016 (Why is no real title available?)
- On relativized nondeterministic polynomial-time bounded computations
- More about Exact Slow $k$-Nim
- scientific article; zbMATH DE number 6520244 (Why is no real title available?)
- Nontriviality for Exponential Time w.r.t. Weak Reducibilities
- A logic for PTIME and a parameterized halting problem
- On Relativized Polynomial and Exponential Computations
- Bi-immune sets for complexity classes
- scientific article; zbMATH DE number 3926244 (Why is no real title available?)
- scientific article; zbMATH DE number 3958736 (Why is no real title available?)
- scientific article; zbMATH DE number 4011940 (Why is no real title available?)
- On relativized exponential and probabilistic complexity classes
- scientific article; zbMATH DE number 4074484 (Why is no real title available?)
- scientific article; zbMATH DE number 4080914 (Why is no real title available?)
- A second step toward the strong polynomial-time hierarchy
- Nontriviality for exponential time w.r.t. weak reducibilities
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- Oracles for Deterministic Versus Alternating Classes
- scientific article; zbMATH DE number 1223623 (Why is no real title available?)
- scientific article; zbMATH DE number 1263206 (Why is no real title available?)
- Towards the Actual Relationship Between NP and Exponential Time
- Beyond \(\mathbf{P}^{\mathbf{NP}}=\mathbf{NEXP}\)
- Almost every set in exponential time is P-bi-immune
- scientific article; zbMATH DE number 227415 (Why is no real title available?)
- Complexity classes of equivalence problems revisited
- Downward translations of equality
This page was built for publication: Relativizations comparing NP and exponential time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3675521)
