New answers tagged complexity-theory
0
You cannot reduce set-packing to your problem, unless P=NP.
There is a linear-time algorithm for your problem.
Remove all vertices of type 1 and all their neighbors. Let $m'$ (resp. $n'$) be the set of remaining vertices in $m$ (resp. $n$).
If $|m'| \ge k$ and the neighborhood of $m$ contains all the vertices in $n'$, the answer is yes.
If any of the ...
2
This is called the Dominating Set problem, and it is indeed NP-hard. In fact, it's in some sense harder than Vertex Cover, since it's not fixed parameter tractable (FPT).
0
Here is a sketch of a direct reduction from 3-SAT to your problem.
Given a formula $\phi$, create a graph that contains:
For each variable $x_i$ of $\phi$: a path of length 2 traversing vertices $x_i, u_i, \overline{x}_i$. Vertex $u_i$ is in $A$ and $g(u_i)=1$.
For each clause $C_j$ of $\phi$, a path of length 2 traversing vertices $v_j, w_j, z_j$. Vertex $...
1
Let $\langle \mathcal{S}, \mathcal{I} \rangle$ be an instance of exact cover. Here $\mathcal{I}$ is a set of items and $\mathcal{S} \subseteq 2^\mathcal{I}$ is a collection of subsets of $\mathcal{I}$.
The goal is to decide whether there is a subset $S$ of $\mathcal{S}$ such that every item in $\mathcal{I}$ belongs to exactly one set in $S$. This is a well-...
0
$n^n$ is a lot larger than n!. The first multiplies n x x n x n x ... x n (n times), the latter multiplies 1 x 2 x 3 x 4 x ... x n. So it is obvious that $O(\log(n^n)) < O(\log(n!))$ is not true. $O(\log(n^n)) > O(\log(n!))$ is less obvious, but also not true.
That's because we are taking the logarithm on both sides. Taking logarithms changes ...
0
No. As a counterexample pick any non-trivial problem $P_2$, i.e., a problem with at least one yes instance $I_{\text{yes}}$ and at least one no instance $I_{\text{no}}$.
To reduce an instance $I_1$ of $P_1$ to an instance $I_2$ of $P_2$ first solve $I_1$ (e.g., by brute force). If the answer to $I_1$ is yes, then let $I_2 = I_{\text{yes}}$, otherwise $I_2 = ...
3
$O(\log n^n)$ and $O(\log n!)$ both describe the same set of functions.
Notice that $( \frac{n}{e} )^n \le n! \le n^n$ and hence:
$O(n \log n) = O(n \log \frac{n}{e}) = O( \log ( \frac{n}{e} )^n) \subseteq O(\log n!) \subseteq O(\log n^n) = O(n \log n)$.
This shows that all the above sets coincide.
1
No, it doesn't prove that P = NP.
This has nothing to do with approximations; it has to do with average-case hardness vs worst-case hardness. The two results are showing that solving the problem for a randomly chosen hypergraph is usually easy; but there exist hypergraphs where the problem is hard. Presumably, choosing a hypergraph at random is very ...
1
Given $\phi$ and an assignment $\overline{y}$, the problem of deciding if there exists a satisfying assignment $\overline{x} \le \overline{y}$ (w.r.t. the lexicographical order) is in NP.
This can be seen by either designing a nondeterministic Turing machine that solves the problem in polynomial time (nondeterministically guess $\overline{x}$, then ...
1
So this is what I consider as the pitfalls of abstracting physical computation into a purely mathematical theory. First, to answer your question, by extended Church-Turing, when you implement your algorithm on a physical RAM machine, it will run in exponential time.
There are some subtle points here.
To access a uniformly random memory cell among all $2^n$ ...
1
What $0^{|w|^2-|w|-1}$ is? It is "$0$" symbol repeated $|w|^2-|w|-1$ times. What is time complexity of simply outputting $0$ $|w|^2-|w|-1$ times? Clearly it is $|w|^2-|w|-1$, what is $O(|w|^2)$, i.e. polynomial of length of input.
3
This statement is to my knowledge unknown. If this is an exercise, then it is likely an error: did they mean $RP$ instead of $ZPP$?
Since $k$-coloring is NP-complete, what you are asked to show is:
If $NP \subseteq BPP$, then $NP = ZPP$.
First, let's review what is known: the basic inclusions are the following:
\begin{align*}
P \subseteq ZPP \subseteq ...
15
The monotone version of X3SAT that your proof is based on has the nice property that setting a literal false in one clause will never cause the negation of that literal to be true in another, which means you can say
The only way a conflict can occur is when all literals in a clause are set to false.
and it will be true because forcing two literals false ...
1
Let $f(n) = n^{\log n}$. Then $\mathsf{P} \subseteq \mathsf{DTIME}(f(n))$ while $\mathsf{DTIME}(f(2n+1)^3) \subseteq \mathsf{EXP}$.
(Actually, whether this argument works depends on the exact definition of $\mathsf{DTIME}$. If it doesn't, take $f_C(n) = Cn^{\log n}$ and sum over all integer $C>0$.)
2
Sipser reduces $A_{\mathit{TM}}$ to $\mathit{HALT}_{\mathit{TM}}$. Since $A_{\mathit{TM}}$ is uncomputable, it follows that $\mathit{HALT}_{\mathit{TM}}$ has to be uncomputable. He is using the following general statement:
If $A$ reduces to $B$ and $B$ is uncomputable, then so is $A$.
You are right that this general statement itself is proved by ...
4
Yamakami showed in their paper Analysis of Quantum Functions that the quantum analog of PP is the same as classical PP. This is mentioned in the Wikipedia article on PP.
-1
Perhaps this is a reference to Cobham's thesis https://en.wikipedia.org/wiki/Cobham%27s_thesis?wprov=sfla1. Usually the word used is "feasible" though.
2
No, $\sqrt{n}$ increases far faster than $O(1)$, and $n^{\sqrt{n}}$ grows far faster than $n^{O(1)}$. No, it certainly does not have the same runtime. See Sorting functions by asymptotic growth.
There may be no predefined complexity class; the complexity class is the class of all algorithms who run in time $n^{O(\sqrt{n} \log n)}$, and there's probably ...
3
There is no one true answer. It depends on context. The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time". Polylogarithmic time is used only in very narrow contexts.
In general, if you think your audience might not be sure about ...
3
The complexity class $\Sigma_2^P$, which is the second level of the polynomial hierarchy, consists of all languages $L$ for which there exists a polytime predicate $f$ and a polynomial $p$ such that
$$
x \in L \Longleftrightarrow \exists y \forall z \, f(x,y,z), \text{ where } |y|,|z| \leq p(|x|).
$$
This is the natural location for your problem:
$x$ is a ...
2
You're right. All that matters is that the reduction runs in polynomial time. (It follows that the circuit has polynomial size, since the output of any polynomial-time algorithm must be polynomial in length.)
Given a circuit with multiple inputs, you can force some of the inputs to 0 or 1. If the circuit has polynomial size, this modification takes ...
1
Suppose that $L = \{x \mid \exists y R(x,y)\}$, where $R(x,y)$ is a decidable predicate.
To recognize $L$, given an input $x$, enumerate all possible $y$, and check whether $R(x,y)$ holds for at least one of them. This will halt iff $x \in L$.
2
Showing that this your problem is in NP is easy.
To show that your problem is NP-hard, reduce from PARTITION. The reduction simply chooses a large enough modulus $k$. Details left to you.
3
NP-completeness is a category of decision problems, that is, problems in which the answer is Yes or No. When we say that 3SAT is NP-complete, what we mean is that the decision version of 3SAT is NP-complete.
There are other types of problems around. The three most common ones are optimization problems, function problems and search problems.
Optimization ...
3
Short answer: if you can solve the decision (yes/no) problem, calling that tells you if it has no solution; if there is a solution, pick a variable and set it to true, see if the result can be satisfied; if not, it has to be false. This way, with one call to the oracle per variable you get a "solution" (set of values of the variables making the expression ...
2
Check Belare and Goldwasser, "The complexity of decision versus search", SIAM J. Of Computing, 23:1 (feb 1994), pp. 97-119. Belare has notes for a class.
3
The brute force solution enumerates all permutations. You can easily encode each permutation using $n\log n$ bits, since you can encode it as a list of numbers from $1$ to $n$, and each number takes $\log n$ bits to encode. You can check that a given permutation corresponds to a tour using $O(\log n)$ additional bits of space, so in total the space ...
6
Turing machines are a nice model with several advantages, mostly their simplicity, but they are not the first choice when analyzing algorithms. Algorithms are typically implicitly analyzed on the RAM machine model, and in some cases, on the BSS model.
Here are some comments on the computational complexity of counting in various models:
Single-tape Turing ...
1
You should measure the length of the output in the same way you measure the length of the input.
For example, when computing the identity function $f(m) = m$, an input $m$ has input length $n = \Theta(\log m)$ and output length also $n$, which is polynomial in $n$.
The factorial function, in contrast, has much too long output length. Indeed, if the input ...
2
Your problem is #P-hard. Indeed, given a #SAT instance with variables $x_i$ and clauses $C_j$, let $\kappa_{i,b}$ be the product of the clauses $C_j$ satisfied by the truth assignment $x_i=b$, and consider
$$ P = \prod_i (\kappa_{i,0} + \kappa_{i,1}). $$
The coefficient of $\prod_j C_j$ in $P$ is the number of satisfying assignments.
In the other direction, ...
1
Use nondeterminism to guess an index $i$ for which $w_i \neq w_{i+1}$. The machine reads its input until it nondeterministically chooses a $w_i$ and places it on the stack. Afterwards, it compares $w_{i+1}$ to the content on the stack symbol by symbol. If the comparison fails, the machine accepts.
2
Assuming that every vertex of $G$ has degree $2$, no clique of $G$ can have more than $3$ vertices. Then $\textrm{2d-CLIQUE}$ is trivially in $\textrm{P}$ and, if $\textrm{P} \neq \textrm{NP}$, it cannot be $\textrm{NP}$-complete.
Under the above assumption (which is trivial to check), $(G,k) \in \textrm{2d-CLIQUE}$ iff one of the following conditions holds:...
Top 50 recent answers are included
