New answers tagged complexity-theory
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 ...
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.
3
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 $\...
0
I got it: this algorithm has a nearly-constant complexity, specifically the complexity is $\Theta(\log^{*}(n))$ where $\log^{*}(n) \le 5 \ \forall n \le 2^{16}$
0
If $L_1$ is recursive and $L_1 \le_p L_2$, they it is possible that $L_2$ is not recursively enumerable (and hence not recursive).
For example pick $L_1 = \emptyset$ and $L_2$ as the set of (a suitable encoding of) all Turing machines that do not halt on empty input.
Clearly $L_2$ is not recursively enumerable. A possible Karp reduction from $L_1$ to $L_2$ ...
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+...
0
Pick any unsatisfiable CNF SAT instance.
Transform the CNF to 3-SAT.
The new instance is an element of 3-co-SAT.
Any unsatisfiable satisfiability instance undergoing the same 3-SAT CNF transformation is an example of 3-co-SAT.
0
The formula
$$(x\vee y \vee z) \wedge (\overline{x}\vee y \vee z) \wedge(x\vee \overline{y} \vee z) \wedge(x\vee y \vee \overline{z}) \wedge(\overline{x}\vee \overline{y} \vee z) \wedge(\overline{x}\vee y \vee \overline{z}) \wedge(x\vee \overline{y} \vee \overline{z}) \wedge(\overline{x}\vee \overline{y} \vee \overline{z})$$
is in $3$-co-SAT.
2
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-...
1
All of these classes can be described as consisting of languages accepted by certain Arthur–Merlin games. In these games, Merlin, an unlimited but potentially dishonest party, tries to convince Arthur, a probabilistic Turing machine, that the input $x$ belongs to the language $L$. We ask that if $x \in L$ then some Merlin convinces Arthur with probability at ...
3
If you have a fixed number of variables, then you have a fixed number of assignments $2^{|\text{vars}|}$, so there's a polynomial time algorithm for checking all possible assignments.
2
Russell Impagliazzo described five possible worlds in his classic paper A personal view of average-case complexity. In one of them, Heuristica, P is different from NP, but NP is easy on average (in some specific technical case).
Recent work in meta-complexity has been aiming at ruling out Heuristica. See for example recent work of Shuichi Hirahara.
2
From the paper:
We say that $M$ runs in polynomial time if there exists $k$ such that for all $n$, $T_M(n) \leq n^k + k.$
which means that after $T$ runs for $n^k + k$ steps and hasn't accepted, it can reject because it would have already gone into the 'accept' state if the word were in the language. So 'no' answers are trivially dealt with by such an ...
2
Dantzig's simplex algorithm to solve linear programming problems is exponential in the (extremely unlikely) worst case, the above article cites several polynomial algorithms.
0
Your function is in fact in $\mathsf{NC}^1$.
It is well-known that threshold functions are in $\mathsf{NC}^1$ (see for example this question on cstheory). In particular, the function $\sum_i x_i = w$ is in $\mathsf{NC}^1$ for all $w$. By computing these functions for all $w$, you can easily compute your function in $\mathsf{NC}^1$.
1
There will be no contradiction, since $D$ doesn't run in time $n^{1.4}$. In fact, what the proof of the time hierarchy theorem shows is that no equivalent Turing machine can run in time $n^{1.4}$, precisely because this will result in a contradiction. In other words, the language computed by $D$ lies outside of $\mathrm{DTIME}(n^{1.4})$. On the other hand, $...
0
Even more TLDR:
Problem: Given an input return an output related to the input in some way. Decision problems answer yes/no questions related to the input
Optimization problems seek to minimize or maximize some property related to the input.
Algorithm: a specific instance of solving a problem. Problems may have many algorithms that solve the problem
Language: ...
1
As $\mathrm{SAT}$ is $\mathrm{NP}$-complete, we know that there is a polytime reduction from our language $L$ to $\mathrm{SAT}$. However, this reduction can involve a polynomial blowup of the input size. This means that an input $w$ to $L$ could be mapped to a formula $\phi_w$ such that $|\phi_w| \approx |w|^k$ for some constant $k$.
Running our hypothetical ...
8
The first "approach" is the definition of a polynomial time many-one reduction. This is the type of reductions used for defining NP-hardness: a problem $B$ is NP-hard if for every problem $A$ in NP, there is a polytime many-one reduction from $A$ to $B$.
The second "approach" is the definition of a computable many-one reduction, which is ...
2
Theoretically, we don't know how hard k-SAT is; P ?= NP remains an open question. Empirically, random $k$-SAT at the critical clause/variable ratio for each $k$ seems to require exponentially more effort as the number of variables increases. As an exercise I ran glucose on thousands of random 3-SAT instances with a 4.26 clauses/variables ratio, averaged ...
1
In my_func(a), Recurrence Relation will be
$T(n) =
\begin{cases}
4T\bigg(\frac{n}{2}\bigg)+{n} & \quad \text{if } n \geq 4\\
1 & \quad \text{if } n <4
\end{cases}
$
In new_func(a), Recurrence Relation will be
$T(n) =
\begin{cases}
3T\bigg(\frac{n}{2}\bigg)+{n} & \quad \text{if } n \geq 4\\
1 & \quad \text{if } ...
3
The problem is polynomial-time solvable using a reduction to 0-1 knapsack problem. Take a knapsack of size $W = n+1$. Take $n$ items of size $a_i$ and value $a_i$. The maximum value obtained is $n+1$ if and only if there exists a subset of items that sum to $n+1$.
The 0-1 knapsack problem can be solved in time $O(n \cdot W)$ using dynamic programming. ...
2
No (unless $\mathsf{P}=\mathsf{NP}$), the problem is in $\mathsf{P}$. The following is polynomial-time dynamic programming algorithm.
For $i=0,\dots,n$ and $j=0, \dots, n+1$ let $S[i,j]$ be true iff there exists a subset of $\{a_1, \dots, a_i\}$ whose elements sum up to $j$.
We trivially have that $S[i,0]$ is true for all $i$, while $S[0,j]$ if false for all ...
2
$\Omega(n \log n)$ operations are needed. More precisely, starting from any given tree $T$ you can only reach $\exp(O(n+m))$ other trees in $m$ operations. The idea is to augment your information-theoretic argument with the observation that most operations commute. Note that we cannot hope to replace $O(n+m)$ with $O(m)$, since for $m = 1$ there can be $O(n) ...
Top 50 recent answers are included