# Tag Info

## New answers tagged computational-complexity

-1

The answer is tied to the way that the problem would be solved. Using Logic and Paradoxes to solve this problem, opens a way to Philosophical discussions as GĂ¶del proof did. It seems very probable to solve this problem in this way, in many specialist views. Personally, I think I did it!

1

It's clearly $O(n)$, for here's an algorithm: Set S(0) = 0, min = S(0), minIndex = 0; For i = 1 to n: Compute S(i) = (i-n) * [S(i-1)/((i-1)-n) + x_i]; If S(i) < min: Set min = S(i) and minIndex = i; return minIndex; There's really no hope for improving the efficiency, because there's a sequence $\{x_i\}$ with the property that an alteration to ...

2

Right now there are two competing methods for determining $\pi(x)$ when $x$ is large: the combinatorial method of Meissel-Lehmer-Lagarias-Miller-Odlyzko-Deleglise-Rivat (see here), which requires $O(\frac{x^{\frac{2}{3}}}{(\log x)^2})$ time and $O(x^{\frac{1}{3}}(\log x)^2)$ space, and the analytical method of Lagarias-Odlyzko (see here), which requires $O(x^... 3 There is no holomorphic function (on any neighborhood of$0$) with$f^{(n)}(0) = (n!)^2$, but you can find a$C^\infty$smooth function with arbitrarily prescribed partial derivatives (this is a theorem of Borel). In the complex setup, you can for example ask for a smooth function satisfying $$\frac{\partial^n f}{\partial z^n}(0) = (n!)^2 \qquad \frac{\... 2 When p is a small prime, finding a solution to a^x \equiv b \bmod p is correspondingly easy (assuming that a,b are not divisible by p). For example, 2^x \equiv 28 \bmod 3 holds for any even power x. It is also clear that if a^x \equiv b \bmod p^s for some integer power s\ge 1, then:$$ a^x \equiv b \bmod p^s \implies a^x \equiv b \bmod p^{... 0 This is actually Dominating set problem, check in wikipedia https://en.wikipedia.org/wiki/Dominating_set I think the application is, how to select least number of people in group to tell a message, so that all of the people in the group can get that message via friends. 1 Usually, you reduce the partition problem to the bin packing problem as follows: Let an instance of the partition problem be given by integers$a_1, \ldots, a_n$. Define an instance of the bin packing problem by integers$a_1, \ldots, a_n$and bin size$\frac{1}{2} \sum_{i = 1}^n a_i$. Then the partition problem has a solution if and only if the bin packing ... 0 This sounds like the Vertex-Cover problem, which is NP-Hard. You might consider an approximation algorithm for this problem. One such algorithm is to choose a maximal matching (a greedy algorithm will suffice). The vertices in this matching form a vertex cover. As each edge has two vertices, this is a$2$-OPT approximation algorithm. 0 Let$k>0$. If$T_A(n)$is the cost of the algorithm$A$for an input of size$n$, saying that$A$is$O(k)$is saying that$T_A(n)$is$O(k)$, which means that there are constants$m_A$and$M_A$such that$T_A(n)\le kM_A$whenever$n\ge m_A$. Suppose that$A$is$O(k)$, and let $$M=\max\{kM_A,T_A(0),T_A(1),\ldots,T_A(m_A-1)\}\;;$$ Clearly$T_A(n)\le ...

2

Solve the system in $\mathbf Z/2\mathbf Z$. Run the full row reduction algorithm on its augmented matrix: $$\left[\begin{array}{ccc|c} 1&1&1&0\\ 1&0&1&1\\1&1&0&1 \end{array}\right]\rightsquigarrow\left[\begin{array}{ccc|c} 1&1&1&0\\ 0&1&0&1\\0&0&1&1 \end{array}\right]\rightsquigarrow\... 1 The stopping condition used in the video is a bit unusual for bisection, but would be very common for other techniques. He is stopping once |g^2-x|<\epsilon where g is the current guess. He is not stopping once |g-\sqrt{x}|<\epsilon, even though in bisection one can proceed this way. Here |g^2-x| is called the forward error and |g-\sqrt{x}| ... 1 Hint: For some M_0 and w_0 consider the function$$ f(n) = \begin{cases} \bot & \text{ if $M_0(w_0)$ halts in exactly $n$ steps} \\ 0 & \text{otherwise} \end{cases} $$Does L contain the machine that computes f in the straightforward way? 1 NP-hardness of your \lceil \log n\rceil-SAT follows immediately by the fact that \lceil \log n\rceil \ge 3 whenever n\ge 5 -- and instances with less than 5 variables are easy anyway. (Note that you can convert a k-SAT instance to a K-SAT for K>k simply by adding redundant literals to each clause.) k(n)-CLIQUE is hard for at least some ... 0 1) Yes- your formalization makes sense. Is A(n) NP-Hard for an arbitrary fixed n \in \mathbb{N}? I don't know. 2) A reduction from an existing NP-Hard problem L to A(n) would suffice. Note that for each instance \omega \in L, you must transform \omega to a graph in A(n). Furthermore, your transformation cannot take any string not in L to a ... 0 You have to be careful because performing row operations on A does not preserve the eigenvalues of A since row operations correspond to changing A to PA for some invertible P there is no reason that PA will be similar to A in general. For example, the eigenvalues of$$ A = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}  are $\lambda = ... 0 A Boolean function in DNF tells you explicitly which configurations satisfy it. This is feasible to determine in polynomial time. We iterate through the products to determine if one does not contain both a variable and its negation. If one such product is found, configure the variables so that product is$1\$. Then the Boolean function is satisfiable. This is ...

Top 50 recent answers are included