214

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 ...


47

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 ...


40

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 ...


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 ...


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

I think it depends on what you're interested in. If you're looking for an exact solution to a problem and you hear that it's either NP-hard or PSPACE-hard, then in either case you won't be able to find an algorithm for that problem that is simultaneously worst-case efficient, deterministic, and always correct unless P = NP or P = PSPACE. Therefore, if you're ...


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

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

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

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

A machine running in exponential time could use exponential space. So a priori it could be that machines restricted to polynomial space would be weaker. A similar situation occurs for P and L. A machine running in polynomial time could use polynomial space, so a priori it could be that machines restricted to logarithmic space would be weaker. It is even ...


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

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 ...


9

From the P vs. NP and the Computational Complexity Zoo video. For a computer with a really big version of a problem... P problems easy to solve (rubix cube) NP problems hard to solve - but checking answers is easy (sudoku) Perhaps these are all really P problems but we don't know it... P vs. NP. NP-complete Lots of NP problems boil down to the same ...


9

No. Counting independent sets in graph is #P-hard, even for 4-regular graphs but Dror Weitz gave a PTAS for counting independent sets of $d$-regular graphs for any $d\leq5$ [3]. (In the model he writes about, counting independent sets corresponds to taking $\lambda=1$.) Computing the permanent of a 0-1 matrix is also #P-hard (this is in Valiant's original #...


9

The reduction takes time to perform. You know that time is polynomial but you don't know it's linear so you can't conclude that $L\in \mathrm{NTIME}(n)$. You can only conclude that $L\in\mathrm{NTIME}(n^k)$ for some $k$ which, of course, you already knew from the assumption that $L\in\mathrm{NTIME}(n^3)$.


9

Solving intersection Non-Emptiness for 2 DFA's: It essentially just becomes a reachability problem for the product DFA. Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ space. Or, we can solve it non-deterministically with $O(\log(n))$ space. By Savitch's Theorem, we can also solve it deterministically in $2^{O(\log^2(n))}$ time ...


9

$\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>0$. That this union is, in fact, equal to $\mathrm{DTIME}(cn)$ for any given $c>1$ (i.e., $1+\varepsilon$) means that all the $\mathrm{DTIME}(cn)$ for $c&...


9

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 advice of length $a(n)$. More formally, $L\in T(n)/a(n)$ if there exists a Turing machine $M(x,y)$ and a sequence of strings $\left\{\alpha_n\right\}_{n\in\mathbb{N}...


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