# Tag Info

### Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

No, there will be absolutely no implication, for several reasons: The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard ...
• 278k

### Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

No implications are known either way: classical simulation of quantum computers tells us nothing about how hard NP search problems are; fast solutions to NP search problems tell us nothing about how ...
• 4,372
Accepted

### Do any decision problems exist outside NP and NP-Hard?

If $P = NP$, then any non-trivial language is NP-hard, and any trivial language belongs to NP. Hence, we do not get anything which is neither NP or NP-hard in this case. If, however, $P \neq NP$, ...
• 3,183
Accepted

### Notation: SPACE(n) vs SPACE(O(n))

It depends on what definitions you use. Sipser [1] defines $\mathrm{SPACE}(f(n))$ to be the class of languages decided by Turing machines using $O(f(n))$ cells on their work tapes for inputs of ...
Accepted

### Can any problem in P be converted to any other problem in P in polynomial time?

If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$. Here "non trivial" means that $B$ has at least ...
• 29.5k
Accepted

### If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?

Your prof was absolutely not rigorous (i.e. completely wrong), that's why the distinction between NP and co-NP doesn't make sense with his definition. Better definition: Def.: A decision problem (...
• 31.1k
Accepted

### Complexity classes pertaining to listing all solutions?

The concept you are looking for is called enumeration complexity, which is the study of the computational complexity of enumerating (listing) all the solutions to a problem (or the members of a ...
• 1,301
Accepted

• 278k

### What is the relation between EXPTIME and NP HARD complexity classes?

The two classes are incomparable: neither is a subset of the other. There are problems in EXPTIME that are not NP-hard. The languages $\emptyset$ and $\Sigma^*$ are both in EXPTIME but are definitely ...
Accepted

### Oracle Turing Machine EXP^EXP

No, $\mathsf{EXP^{EXP}=2EXP}$, a set of languages decidable in $O\left(2^{2^{\mathrm{poly}(n)}}\right)$ time. This is just because you can give exponentially long input to an oracle which can solve ...
• 1,736
Accepted

### Is every PSPACE-complete problem complete with respect to logspace reductions?

If every PSPACE complete problem is also complete under logspace reduction, then $\mathsf{P\neq PSPACE}$. To see why, suppose for the purpose of contradiction that the definition of completeness ...
• 13.4k
Accepted

### Is DISCRETE LOG a NP hard problem?

No one knows, but: It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof. (Evidence for the suspicion: they are in NP $\cap$ coNP. See, e.g., https://...
• 162k
Accepted

### If NP is not a proper subset of coNP, why does NP not equal coNP?

$\{2,3\}$ is not a proper subset of $\{3,4\}$, yet the two clearly are not equal. Comparing sets is not like comparing numbers: two sets might not be comparable. Additionally, NP is not a subset of ...
• 29.8k
Accepted

• 151

### What does the complexity class $\mathsf{XP}$ stand for?

There is a slightly different description for XP which I personally find less misleading: "Polynomial time for each parameter". I believe the zoo page uses FPT instead of P for some formal reasons (...
• 2,288

### PSpace-completeness under PSpace reductions

Every language $X$ in PSPACE would be complete under your proposed definition, except for $\emptyset$ and $\Sigma^*$. You could reduce any PSPACE language $Y$ to $X$ by a reduction that ...
Accepted

### Looking for a problem provably not in P

The time hierarchy theorem already does the diagonalization for you. Let $X$ be any $\mathbf{EXP}$-complete problem. If $X\in\mathbf{P}$, then $\mathbf{EXP}=\mathbf{P}$, since we can solve any ...
No. $\Sigma^*\in\mathbf{P}$ and every langauge is a subset of that – even undecidable ones.