Skip to main content
41 votes

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 ...
Yuval Filmus's user avatar
22 votes

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 ...
Lieuwe Vinkhuijzen's user avatar
14 votes
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$, ...
Arno's user avatar
  • 3,183
14 votes
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 ...
David Richerby's user avatar
14 votes
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 ...
Steven's user avatar
  • 29.5k
12 votes
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 (...
gnasher729's user avatar
  • 31.1k
11 votes
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 ...
mdxn's user avatar
  • 1,301
10 votes
Accepted

Is DTIME(n) = DTIME(2n) true? (unlike Rosenberg's results)

$\mathrm{DTIME}(O(n))$ is the set of problems that can be solved in deterministic $O(n)$ time for some constant implicit in $O$, in other words, it is the union of the $\mathrm{DTIME}(cn)$ for all $c&...
Gro-Tsen's user avatar
  • 393
10 votes
Accepted

Why is PH in PSPACE?

No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, ...
Tom van der Zanden's user avatar
9 votes

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

There are NP-hard problems that are not in EXPTIME and vice versa. This is to be expected as NP-hard is defined by a lower bound and EXPTIME mainly by an upper bound. NP is contained in EXPTIME, ...
Pontus's user avatar
  • 687
9 votes
Accepted

Why does P/Poly can also receive bad advice?

Lets review the definition of the class $P/poly$ by Turing machines which take advice. The class $T(n)/a(n)$ is the set of languages decidable by a Turing machine which runs in time $T(n)$ with ...
Ariel's user avatar
  • 13.4k
9 votes
Accepted

Known problems in BQP \ NP?

If there was a problem known to be in $\text{BQP}$ but not $\text{NP}$, that would prove $\text{BQP} \not\subset \text{P}$. But $\text{BQP}$ vs $\text P$ is also still an open problem. It is ...
Craig Gidney's user avatar
  • 5,862
9 votes

What is the definition of P, NP, NP-complete and NP-hard?

P, NP, NP-complete and NP-hard are complexity classes, classifying problems according to the algorithmic complexity for solving them. In short, they're based on three properties: Solvable in ...
Thomas C. G. de Vilhena's user avatar
8 votes
Accepted

Is NEXP = co-NEXP?

It is known that $\mathsf{NP} = \mathsf{coNP}$ implies $\mathsf{NEXP} = \mathsf{coNEXP}$, using a padding argument. However, both are considered unlikely. The difference between classes like $\mathsf{...
Yuval Filmus's user avatar
8 votes

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 ...
David Richerby's user avatar
8 votes
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 ...
rus9384's user avatar
  • 1,736
8 votes
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 ...
Ariel's user avatar
  • 13.4k
8 votes
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://...
D.W.'s user avatar
  • 162k
7 votes
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 ...
Joey Eremondi's user avatar
7 votes
Accepted

$\mathsf{PP=RP}$ consequences

$\newcommand{\co}{\mathsf{co}\text{-}}$ $\newcommand{\class}[1]{\mathsf{#1}}$ If $\class{PP}=\class{RP}$ then you have a collapse to the first level, namely $\class{PH}=\class{NP}$. Assume $\class{...
Ariel's user avatar
  • 13.4k
7 votes
Accepted

Is complexity class $\Sigma^1_1$ from polynomial hierarchy decidable?

The confusion lies in using the same notation for the polynomial hierarchy and the arithmetical hierarchy. The similarities are obvious, both notations talk about formulas with increasing quantifier ...
Ariel's user avatar
  • 13.4k
7 votes
Accepted

Is exponentiation in P?

Your problem is not in P, for two different reasons: P is a class of decision problems, but your problem is a function problem. Instead of P, you should consider its functional equivalent FP. The ...
Yuval Filmus's user avatar
7 votes
Accepted

Are any "standard" complexity classes uncountably infinite?

Nonuniform complexity class P/poly is uncountable. We can just choose for each input length its own circuit, so for any subset $S \subset \mathbb{N}$ the language $L_S = \{w \colon |w| \in S \}$ is in ...
Vladimir Lysikov's user avatar
6 votes
Accepted

Does NP = coNP imply the collapse of PH to level 1?

No. $PH=NP$ doesn't imply $P=NP$, because $PH$ is not the same class as $P$. Roughly speaking, $PH$ includes $P$, $NP$, $coNP$, and more: $PH$ includes $\Sigma_i$ and $\Pi_i$ for all $i$. Formally, ...
D.W.'s user avatar
  • 162k
6 votes

Proofs of $P^{\#P}\subseteq P^{PP}$ and $\#P\subseteq FP^{PP}$

This is not the full proof but the complete idea: Let Turing machine $M$, define $L_M$ be the language defined as $L_M = \{ ((x, y) \in \Sigma^*\times \mathbb{N} ~|~ \#\text{accepting path of } {M}...
Thinking's user avatar
  • 151
6 votes

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 (...
kne's user avatar
  • 2,288
6 votes

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 ...
David Richerby's user avatar
6 votes
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 ...
David Richerby's user avatar
6 votes

If a language is contained in other langauge, is it of the same complexity?

No. $\Sigma^*\in\mathbf{P}$ and every langauge is a subset of that – even undecidable ones.
David Richerby's user avatar
6 votes
Accepted

Is there a complexity class QPP?

Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible