# Tag Info

419

I think the Wikipedia articles $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good. Still here is what I would say: Part I, Part II [I will use remarks inside brackets to discuss some technical details which you can skip if you want.] Part I Decision Problems There are various kinds of computational problems. However in an ...

208

Part II Continued from Part I. The previous one exceeded the maximum number of letters allowed in an answer (30000) so I am breaking it in two. $\mathsf{NP}$-completeness: Universal $\mathsf{NP}$ Problems OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of efficiently verifiable problems ($\mathsf{NP}$). As ...

74

It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P and NP are both countable.

44

Let's refresh the definitions. PSPACE is the class of problems that can be solved on a deterministic Turing machine with polynomial space bounds: that is, for each such problem, there is a machine that decides the problem using at most $p(n)$ tape cells when its input has length $n$, for some polynomial $p$. EXP is the class of problems that can ...

39

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 problems in polynomial time (which we don't expect them to be able to do), it could still be the case that classical computers cannot solve them in polynomial ...

28

More than useful mentioned answers, I recommend you highly to watch "Beyond Computation: The P vs NP Problem" by Michael Sipser. I think this video should be archived as one of the leading teaching video in computer science.! Enjoy!

22

No. It is another open problem and certainly related, but different. The complexity class co-$\mathsf{NP}$ is the set of languages whose complements are in $\mathsf{NP}$; that is, the set of decision problems for which a "no" answer has a deterministic polynomial-time verifier. So for example, the question "Is this SAT formula unsatisfiable?" If the answer ...

22

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard. It is perfectly possible for other specific classes of instances to be solvable in polynomial time. Consider for example the problem of finding a 3-coloration of a graph. It is a well-known NP-Hard problem. Now imagine that its instances are restricted ...

21

Just elaborating what @Lamine pointed out : When $k$ is part of the input, $k$ can be as large as $\frac{n}{2}$, in which case the number of potential clique sets are $\binom{n}{\frac{n}{2}}$ which is at least $\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$. Hence your naive algorithm would take time $2^{\frac{n}{2}}$ which is clearly exponential in ...

20

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 fast quantum computers can be simulated classically. The following scenarios are possible: $P=NP=BQP$ $P=NP\subsetneq BQP$ $P\subsetneq NP=BQP$ $P\subsetneq NP\... 19 It is maybe easier to consider the contrapositive, that is${\sf P}={\sf NP} \Rightarrow {\sf NP}={\sf coNP}$. So assume${\sf P}={\sf NP}$, then for every$L\in {\sf NP}$, we have$L\in {\sf P}$, and since the languages in${\sf P}$are closed under complement,$\bar L\in {\sf P}$and therefore$L\in {\sf coNP}$. for every$L\in {\sf coNP}$, we have$\...

17

Any problem in NP is in EXPTIME because you can either use exponential time to try all possible certificates or to enumerate all possible computation paths of a nondeterministic machine. More formally, there are two main definitions of NP. One is that a language $L$ is in NP iff there is a relation $R$ such that there is a polynomial $p$ such ...

16

First of all, the question you are asking is open, since an affirmative answer shows that $\sf NP = coNP$. In fact it is one of the most prominent open problems in computer science. If $\sf P= NP$, then the class $\sf NP$ is closed under complement since $\sf P$ is. If on the other hand $\sf P \not = NP$ then we cannot say whether $\sf NP = coNP$ or not. ...

16

All the classes you mention are classes of languages, formally, even if P and NP are often discussed in different (more sloppy?) terms. Note that terminology revolving around decision problems is equivalent to formal languages; the decision is always whether a word is in the given language, i.e. the problem is to solve the word problem. What you need to do ...

15

Let me answer your questions in order: By definition, a problem has an FPTAS if there is an algorithm which on instances of length $n$ gives an $1+\epsilon$-approximation and runs in time polynomial in $n$ and $1/\epsilon$, that is $O((n/\epsilon)^C)$ for some constant $C \geq 0$. A running time of $2^{1/\epsilon}$ doesn't belong to $O((n/\epsilon)^C)$ for ...

14

No, special cases can be easier. Consider this IP, for example, given $a_i \geq 0$ for $i \in [1..n]$: $\qquad\displaystyle \min \sum_{i=1}^n x_ia_i$ s.t. $\quad\displaystyle\sum_{i=1}^n x_i \geq 1$ and $\ \displaystyle x_i \in \mathbb{N}$ for $i \in [1..n]$. It finds the minimum among $a_1, \dots, a_n$ (that for which, inevitably, $x_i=1$ in an optimal ...

14

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 length $n$. Papadimitriou [2], on the other hand defines it to be the class of languages decided by Turing machines using at most $f(n)$ cells on the ...

14

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 one yes instance $I_Y$ and at least one no instance $I_N$ (i.e., the language associated to $B$ is not $\emptyset$ nor $\Sigma^*$). To map an instance $I_A$ of $... 13 The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in Schöning's A uniform approach to obtain diagonal sets in complexity classes shows that there exists some language in NP – co-NP which is NP-intermediate. So NPI ... 12 Vor's answer gives the standard definition. Let me try to explain the difference a bit more intuitively. Let$M$be a bounded error probabilistic polynomial-time algorithm for a language$L$that answers correctly with probability at least$p\geq\frac{1}{2}+\delta$. Let$x$be the input and$n$the size of the input. What distinguishes an arbitrary$\...

11

Copying my answer to a similar question on Stack Overflow: The easiest way to explain P v. NP and such without getting into technicalities is to compare "word problems" with "multiple choice problems". When you are trying to solve a "word problem" you have to find the solution from scratch. When you are trying to solve a "multiple choice problems" you have ...

11

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$, then there are languages which are neither in NP nor NP-hard. For example, we can consider the language $\{1^n \mid \text{the } n\text{-th TM halts}\}$. As this ...

11

Your problem is known as the $\text{UNIQUE-SAT}$ problem which is $\mathsf{US}$-complete. The problem is in $\mathsf{D^p}$ but not known to be $\mathsf{D^p}$-hard under deterministic polynomial time reductions, where the class $\mathsf{D^p} = \{ L_1 \cap \overline{L_2} \mid L_1,L_2 \in \mathsf{NP} \}$. It was shown by Papadimitriou and Yannakis [1] that ...

11

There are very many natural complete problems for $\Pi_2^p$, and there is a survey [1] on completeness for levels of the polynomial hierarchy, containing many such problems. The paper On the complexity of min-max optimization problems and their approximation [2] contains a nice overview of "min-max problems" with several proofs of completeness. The latter ...

11

Here are some known results: $\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular languages. For proofs, see the Wikipedia page on $\mathsf{DSPACE}$. $\mathsf{DCFL} \subseteq \mathsf{SC}$, where $\mathsf{DCFL}$ is the set of deterministic ...

11

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 language/set). Enumeration algorithms can be modeled as a two step process:a precomputation step and an enumeration phase with delay. Both of these steps have their ...

11

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 (that is a problem where the result is either YES or NO and nothing else) is in NP if for every instance where the result is YES there exists a hint such that we ...

10

That looks correct to me. The difference between BPP and PP is that for BPP the probability has to be greater than $1/2$ by a constant, whereas for PP it could be $1/2+ 1/2^n$. So for BPP problems you can do probability amplification with a small number of repetitions, whereas for general PP problems you can't.

10

Only in one direction. As $\mathsf{P}=\text{co-}\mathsf{P}$, if $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ then we would know that $\mathsf{P}\neq\mathsf{NP}$. However the reverse implication doesn't hold. If $\mathsf{P}\neq\mathsf{NP}$ then it's possible that either $\mathsf{NP}\neq\text{co-}\mathsf{NP}$ or $\mathsf{NP}=\text{co-}\mathsf{NP}$.

10

First of all, we don't know whether $NP=EXP$ or not. So the initial answer is "it is an open question". However, we strongly believe (and there are supporting evidence) that $NP\neq EXP$. In fact, we believe that $NP\neq PSPACE$ and that $PSPACE\neq EXP$ (that is, there is a strict containment $NP\subsetneq PSPACE \subsetneq EXP$). Since you are looking ...

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