Tag Info

Hot answers tagged complexity-theory

9

The existence of such an algorithm would imply co-NP is included in NP which is unlikely Checking that a formula is satisfiable: NP, generate proof by providing a solution Checking that a formula is unsafisfiable: co-NP, generating proof can be harder, in classical proof systems the shortest proof of unsatisfiability of an arbitrary formula can be ...

5

Let me recap the proof. We are given a sparse NP-hard language $A$: for each length $n$, there are at most $n^c$ strings of length $n$ in $A$. For a satisfiable CNF $\varphi$, let $a(\varphi)$ be the lexicographically first satisfying assignment for $\varphi$. We consider the NP language $B$, which consists of all pairs $(\varphi,w)$ such that $\varphi$ is ...

4

Yes, a 3-SAT formula $\phi$ can be transformed into a 1-in-3 SAT formula $\phi'$ while preserving the number of satisfying assignments. To avoid ambiguities I will use "$\vee$" between literals of a 3-SAT clause, and commas between literals of a 1-in-3 SAT clause. Let me preliminarily show that, given two literals $a$ and $b$, we can simulate a new type of ...

4

You need to decide whether you want to talk in terms of decision problems (dealing with classes like $\textrm{P}$ or $\textrm{NP}$) or with function problems (dealing with classes like $\textrm{FP}$ or $\textrm{FNP}$). If you choose to talk in terms of decision problems, then the decision problem is to decide, given $(m, n)$, whether it is true that $m = 2^... 4 There are at least two ways to do it. The first is to take a disjoint sum of$B$and$C$, which can be done in many ways, for example $$\{0x : x \in B\} \cup \{1y : y \in C\}.$$ The second is to use an NP-complete language$L$as an oracle. Since any problem in NP reduces to$L$in polynomial time, you can simulate a$B$-oracle using an$L$-oracle. 3 Your statement holds for all oracles$A$iff$\mathsf{P} \neq \mathsf{NP}$. Indeed, if$\mathsf{P} \neq \mathsf{NP}$then your statement vacuously holds. Conversely, if$\mathsf{P} = \mathsf{NP}$, then your statement fails for a random oracle$O$, since such an oracle satisfies$\mathsf{P}^O \neq \mathsf{NP}^O$almost surely. A similar argument shows that ... 3 Such a reduction is described in Appendix B of Régis Barbanchon, On unique graph 3-colorability and parsimonious reductions in the plane. Barbanchon attributes it to previous work ([9] in the bibliography). Elsewhere, I have seen an attribution to Schaefer's celebrated paper in which he proves his famous dichotomy theorem, among else giving a reduction from ... 3 Every language in NP has a logspace verifier. Indeed, let$L$be any language in NP. Therefore, there is a polynomial time machine$T$and a polynomial$p$such that$x \in L$iff some string$y$of size at most$p(|x|)$makes$T(x,y)$accept. While the witness$y$may be hard to check, we can make help a logspace machine verify it by including the ... 3 It's because there are other algorithms (like interior point methods) which run in polynomial time for solving the problem. Even with that being said, it is perfectly possible that the simplex method will outperform them in practice. 3 There exist polynomial time algorithms for solving linear programs. These include the ellipsoid algorithm and interior-point methods. See Wikipedia. 3 Given a graph, does it have a cycle of length$3$($4$)? Four-cycles there is an easy algorithm that requires$O(n^2)$time. The best known algorithm for triangle detection is related to matrix multiplication and has complexity$O(n^\omega)$where$\omega$is the matrix multiplication exponent. It is an open problem to determine whether$\omega=2$. Given a ... 3 Intuitively, the difficulty of all$\mathsf{NP}$-Complete problems is related: solving any single$\mathsf{NP}$-Complete problem in time$O(t(n))$immediately yields an algorithm for any other$\mathsf{NP}$-Complete problem with a running time of$O(t(\mbox{poly}(n)))$. This shows, for example, that either all$\mathsf{NP}$-Complete problems admit polynomial-... 3 No, they are not in general - and focusing on the halting problem specifically makes the situation look more complicated than it actually is. The real point is the following: There are lots of separation results which relativize to all oracles. There's a slight technical issue here, actually: how exactly should we treat space-based complexity classes in ... 3 The answer is no, and the reason is that$\mathrm{P}$is trivially closed under complement. Just by definition of$\mathrm{co}$, it follows that$\mathrm{coNP} = \mathrm{P}$is equivalent to$\mathrm{NP} = \mathrm{coP}$, and then we use that$\mathrm{coP} = \mathrm{P}$to conclude that$\mathrm{coNP} = \mathrm{P}$iff$\mathrm{NP} = \mathrm{P}$. 3 The exact equation is (if$T(1) = 1$): $$T(n) = 2T(n-1) + 1 = 2(2T(n-2) + 1) + 1 =$$ $$2^2 T(n-2) + 2 + 1 =$$ $$2^2(2T(n-3) + 1) + 2 +‌ 1 = 2^3 T(n-3) + 2^2 + 2 + 1$$ Hence,$T(n) = 2^{n-1} + 2^{n-2} + \cdots + 1 = 2^n - 1$(by mathematical induction). 2 The fact that your algorithm is in Java or the source itself are not really relevant. That said, your algorithm requires time$\Theta(n \cdot k)$, where$n$is the length of the input sequence, and$k$is the length of the desired subsequence. This can be as bad as$\Theta(n^2)$, when$k=\Theta(n)$. You can improve the time complexity of your algorithm to$...

2

Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. Since $f$ is injective, if $w \in L$ then there is exactly one witness $z$, and so $L \in \mathsf{UP}$. Since $L$ is always in $\mathsf{NP}$ (using the very same ...

2

Let $L$ be any language in NP. Since $A$ is NP-hard, there is a polytime reduction $f$ such that $x \in L$ iff $f(x) \in A$. We want to convert $f$ to a polytime reduction $g$ such that $x \in L$ iff $g(x) \in A \cup B$. What prevents $f$ from working? Let's consider three cases: $f(x) \in A$. In this case, $f(x) \in A \cup B$ as well. $f(x) \notin A$, and ...

2

Given an instance $x$ of $A$, reduce it to an instance $y$ of $A \cup B$ as follows: Check (in polynomial time) if $x \in B$, if the answer is yes, then $x \not\in A$ since $A \cap B = \emptyset$. Pick any $y \in \Sigma^* \setminus (A \cup B)$ (which is non-empty by hypothesis). If $x \not\in B$, then $x \in A \cup B \iff x \in A$. Pick $y=x$.

2

(other than bounding the complexity of verification to polynomial time). This is exactly the reason the problems can be solved in exponential time. An algorithm can simply run the verification algorithm for all possible certificates to see if any one of them is a valid "solution". There are only exponentially many certificates since the definition of $NP$ ...

2

For any fixed $k$, $O(\binom{V}{k}) = O(V^k)$ is polynomial, whereas $O^*(1.47^{V-k}) = O^*(1.47^V)$ is exponential. Exponentials grow much faster than polynomials. Plotting the curves is not so helpful, since these are asymptotic statements. That said, if you're interested in particular $V$ and $k$, then your best option is to empirically check which of ...

2

The problem is not clear enough. Turing Machines can or cannot solve problems if those problems are languages, that means, sets of strings over a finite alphabet. You cannot represent all reals in this way, so it is not even a problem that a TM could even attempt to solve. In the same fashion that world hunger is not a problem in the precise sense that a ...

2

Yes, we can transform an epsilon NFA into a NFA by keeping the same state set, basically adding new edges. If there is an $\varepsilon$ path from state $p$ to state $q$, and an edge from state $q$ to state $r$, then add an $a$ edge from $p$ to $r$. Also, if from state $p$ we can reach a final state then state $p$ can be made accepting. After these two steps ...

1

What I recommend first is to notice that if you're looking at the complexity of the function $3x^2+2x+1$, really all you should care about is the function $x^2$. because if you will prove that $x^2 = \omega(xlogx)$ then adding the $2x + 1$ won't ruin that proof since $x^2$ is polynomially bigger than $2x + 1$ and so we can just look at the $x^2$. (I will ...

1

The easiest way is to check that $\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = +\infty$, which is a sufficient condition for $3x^3 + 2x +1 \in \omega(x \log x)$. $$\lim_{x \to \infty} \frac{3x^3 + 2x +1}{ x \log x} = \lim_{x \to \infty} \frac{3x^3}{ x \log x} = \lim_{x \to \infty} \frac{3x^2}{ \log x} = \lim_{x \to \infty} 6x^2 = +\infty.$$

1

To answer your first question, this is tremendously unimportant. You typically don't encounter "funny" functions in actual complexity classes you may encounter in practice. Also, the answer to your question might depend on the exact definitions, which is a sign that you shouldn't be considering these complexity classes in the first place. That said, probably ...

1

Both definitions are the same. They just use a different wording. The difference between "decide" and "accept" is commonplace in computability theory, but in complexity theory different terminology is typically used, since we usually deal with machines that always halt. The class $\mathsf{P}$ consists of all languages $L$ for which there exists a Turing ...

1

yet we can't determined such a thing due to the fact that SAT is NP-hard and the "UNSAT" is co-Np-hard.

1

The decision problem "Is the first bit of the input a 0?" can be solved in constant time and space - without reading the whole input. Given that a Turing machine head moves right one step at a time, a Turing machine head can only read a polynomial amount of the proof in polynomial time. While you could define proofs to exceed a polynomial length, only a ...

1

If the matrix has two distinct eigenvalues, you can find them using power iteration. Let $\lambda_1,\lambda_2$ be the 2 eigenvalues, where $|\lambda_1| > |\lambda_2|$. Then you can use power iteration to find $\lambda_1$. Next, set $A' = A - \lambda_1 \text{Id}$. $A'$ is a symmetric matrix with eigenvalues $\lambda_2,0$, so power iteration on $A'$ ...

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