Tag Info

3

$P=coNP$ is an open question, equivalent to the famous: "is $P=NP$ true?" question. The definition of $coNP$ you have is incorrect. The correct definition is the following: $$coNP:=\{L\mid \overline{L}\in NP\}$$ As you can see, it reads $NP$ and not $P$. It was probably a typo wherever you saw that definition.

2

Nondeterministic Turing machines are asymmetric in their treatment of accept and reject states: they accept if any path accepts, and reject if all paths reject. If you swap the accept and reject states of an ordinary Turing machine then it will accept the complement of the language it accepted before, but that isn't generally true of nondeterministic Turing ...

2

Let $H_{f(n)}$ be the set of all pairs $(M,x)$ such that $M$ halts on $x$ within $f(|x|)$ steps. We encode the pairs in such a way that $|(M,x)| = |x| + C_M$, where $C_M$ is a constant that depends only on $M$. Suppose that $H_{f(n)}$ has circuits of size $g(n)$ (note that it's a slightly different $n$). Let $h(n) \leq \kappa 2^n/n$, for an appropriate $\... 1 What people often forget: They have a problem, and the have a sub problem that helps solving the problem. And then they try solving the (hard) sub problem - without realising there is a much better solution. In this case: For every (i, j), 0 <= i <= j < n, find the best way to multiply$A_i$to$A_j$. There are j-i ways to calculate this product by ... 1 You can easily compute the height$h$and the total number of nodes in the recurrence tree. After$h-1$levels, the size of the subproblem is at least$k$and at most$2k$. Therefore,$n/2^{h-1} \geq k$after$h-1$levels. Thus, we get the height of the tree at most$\log (n/k)+1$. Furthermore, the total nodes in the recurrence tree is at most$O(2^{\log n/k+...

1

Consider a star on $n-4$ vertices together with a clique on $4$ vertices.

1

Dinur, Mossel and Regev showed in their paper Conditional hardness for approximate coloring that assuming some variant of the 2-to-1 conjecture (a reduction of the same family as the more famous unique games conjecture), for every $C>4$ it is NP-hard to distinguish between 4-colorable graphs and $C$-colorable graphs. (The recently proved variant of the 2-...

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