New answers tagged complexity-theory
-2
So what is the issue here? The algorithm clearly requires (sqrt(n)//2) divisions by the respect to the N. So if I measure complexity by the function: input number -> #of divisions, then I will get theta(sqrt(n)) complexity.
I believe the actual problem why this algorithm is inefficient that division is not a basic operation, and that the division's ...
2
Yes, such problems can be NP-complete.
Consider classical NP-complete graph problems like clique.
Clique has an $O(2^n)$ time algorithm, where $n$ is the number of vertices. However the input for clique is the adjacency matrix of the graph, which has $n^2$ bits. Therefore when the size of input is measured in bits, clique has an $O(2^\sqrt{n})$ time ...
0
So you suggested the basic technique of checking all pairs which is $O(mn^2)$. Here are some things you can try first, at lower complexity, before falling back to an approach with a similar worst-case bound but likely better constants.
We represent each point $p_i = (x^i_1, \dots, x^i_m)$.
Then clearly there is a dominated pair if $\min_i \max_j x^i_j \leq ...
-1
Also, Another point is that if we use anything except unary base, the problem is NP. for example for binary mode, the length of our number is log(n) and we have (n - 1) numbers before it. So it needs exponential time to decide whether is prime or not.
2
We can construct $S$ such that polynomial-time generators for $A$ exist, while no generator exists for $S^{c}$. Pick $S$ such that all strings starting with $1$ are in it, and exactly half of all strings starting with $0$ are in it.
A sampler that sets the first bit of $x$ to $1$ and outputs it always generates an element in $S$, and generates exactly $\...
2
$O(n \log n)$ is a polynomial speedup over $O(n^2)$, in particular almost a quadratic speedup. $O(n \log n)$ is big-O of $O(n^k$) for all $k > 1$. Its runtime is therefore between linear and any powerfunction whose exponent is strictly greater than 1.
Let $f(n)=n \log n$. Raise it to a power of some value slightly less than 2 to approximate the original ...
4
You can use the following algorithm:
Input: number $n$ encoded in unary
For $k$ from $2$ to $n-1$, check whether $k \mid n$, and if so, output "Not prime".
Output "Prime".
This algorithm runs in time polynomial in $n$.
The AKS test, in contrast, runs in time polynomial in $\log n$, assuming that the input $n$ is encoded in binary. If the input is encoded ...
4
Hint: Notice that your input is unary.
3
I believe you are referring to the accounting method for amortized analysis. With these keywords you should be able to find the explanations you are looking for.
0
Can't answer without solving the P versus NP problem. Because if $P=NP$ then the implication is true since you assumed something false. On the other hand if $P \neq NP$ then the statement is wrong.
So this question is equivalent to asking if P equals NP.
1
If I may make an assumption, you want such a reference to be able to put it in one of your works, right ? I don't why you would wanna do that as if you have a problem A, reducting a NP Hard problem to problem A quite clearly shows that A is NP Hard. No one bothers proving it as it's such a straightforward and fundamental result. If you need to prove it for ...
0
maybe i was a bit to specific, i had a general misunderstanding in how non-deterministic machines work. Here is what i figured:
an accepting nondeterministic turing machine always gives the right answer ("found something, therefore a solution exists",
on the other hand, a reject means "did not find anything" which is not the same as "there is no solution"
...
2
No it does not. The problem DOM considered by the paper seems to be the enumeration of minimal, not minimum dominating sets. Usually minimal means a solution $X$ such that there is no other solution $X'$ with $X' \subsetneq X$. The solution $X$ is not necessarily the minimum size. While minimal dominating sets can be enumerated with polynomial delay in ...
0
First note that $\overline X$ is $\operatorname{co\mathcal{NP}}$-hard since $X$ is $\mathcal{NP}$-hard (try to see why).
Since 3SAT is in $\mathcal{NP}$, any problem that can be reduced to 3SAT is in NP as well. So the statement suggests that the $\operatorname{co\mathcal{NP}}$-hard language $\overline X$ is in $\mathcal{NP}$.
On the other hand, saying that ...
1
The $k$-clique problems asks whether there is a homomorphism from the $k$-clique to a given graph. Therefore in principle, given an instance $\langle G,k \rangle$ of $k$-clique, you can just output $\langle K_k, G \rangle$, which is an instance of graph homomorphism.
However, in general $\langle K_k, G \rangle$ could be much larger than $\langle G,k \rangle$...
1
Regarding the proof of the statement you quoted (to complement Juho's answer):
Let $G$ be a connected planar graph with $V > 2$ vertices, $E$ edges and $F$ faces. We know from Euler's formula that $V-E+F=2$.
Now let us count the number $q$ of $(e,f)$ pairs where $e$ is an edge and $f$ is a face incident to $e$. Because every edge is incident to at most ...
1
The idea is that in a planar graph, there are no cliques of size 5 or more (see Kuratowski's theorem).
So suppose the problem is "is there a clique of size $k$ in a given planar graph $G$?" Now, if $k \geq 5$, we immediately answer NO. If $k \leq 4$, we can simply check every subset of the vertices of size $k$ (note that there are $\Theta(n^k)$ such ...
0
Although, you cannot find the arbitrary constant c from master theorem, you should check using different size inputs which algorithm is faster, because even though both are upper bounded by c*n^2, if we have 4*n^2 and 1/4*n^2, still 1/4*n^2 is 16 times faster !!
A very important point is that your second algorithm seems to use divide and conquer method. ...
2
Because then a Union operation would be very slow: when you Union two trees, you would have to reparent all of the nodes in one of the trees.
2
You had several questions in there, let's just look at a couple of them, the way I understood you.
Is $L \in \textsf{NP} \cap \textsf{coNP}$ "easier" than problems that are $\textsf{NP}$-hard?
Yes, we believe it is (but as gnasher729 points out in a comment, we don't know for sure; $\textsf{NP}$ could still be equal to $\textsf{P}$, in which case the ...
1
There is probably no algorithm that is significantly better than doing a pairwise comparison between all pairs of users.
You can, as you say, memoize (remember) the top-5 match for each user, so that you never have to recompute the top-5 for that user again in the future, but you'll still need to compare that user to each other user at least once. ...
3
Your proof that the problem is in PSPACE is not quite correct. The problem is that the product $n_1 \cdots n_k$ is not bounded by a polynomial in the input length $n_1 + \dots + n_k$. The correct way to do it is to directly apply Savitch's theorem to the NPSPACE machine that nondeterministically guesses a path through the product graph. The difference is ...
1
Yes, your proof of $\Rightarrow$ is correct, but note that you still have to prove the second direction to complete the reduction.
Now we know that IDS is NP-hard
Unfortunately, we don't. We'd need a reduction from SAT to IDS and not the other way around.
To convince yourself of why it makes sense, a reduction from $A$ to $B$ means ...
1
I don't think you're likely to find any such proof. Given our current level of knowledge, as far as we know it is possible that $\textsf{P} \ne \textsf{NP}$ but $\textsf{NP} = \textsf{co-NP}$ (we cannot prove otherwise). If that were true, then we'd have $\textsf{NPC} = \textsf{co-NPC}$ (and thus $\textsf{NPC} \cap \textsf{co-NPC} \ne \emptyset$) yet $\...
2
Yes. $P \subseteq P/\text{poly}$. In particular, every polynomial-time algorithm can be simulated by a family of polynomial-sized circuits: the circuit just emulates the behavior of the algorithm. That this is possible should be pretty clear from the fact that we execute algorithm on CPUs, which are themselves complex circuits built of gates, so it's ...
1
No. Every function can be implemented with a polynomial-depth circuit, but not all function families can be implemented with a polynomial-time algorithm.
In particular, if we're allowed unbounded fan-in/fan-out, you can implement every function in depth 2 using a CNF or DNF formula for the function (but the size of the circuit is exponential). If we're ...
1
There is no deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$. One can prove this with an adversarial argument.
Consider running the algorithm on the following input:
Input #1: $F(x_i,x_i)=1$, and $F(x_i,x_j)=0$ if $i \ne j$.
Keep track of the sequence of pairs $(x_i,x_j)$ of objects that $F$ is evaluated on ...
1
It is enough to pad a special delimiter (say a comma) and $(|x|^2-|x|-1)$ 1's. Suppose $L_\mathrm{pad}= \left\{\left\langle x,1^{|x|^2-|x|-1} \right\rangle : x \in L\right\}$. Since $L\in\mathsf{DTIME}(2^n)$, there is a TM that can determine whether $x\in L$ in $O(2^{|x|})$ time. We then construct a new TM: given a string $y$, it first checks whether $y$ has ...
1
Yes, that's correct. You'll probably have to figure out the polynomial yourself. The way to find the polynomial is to look at the reduction, and from that you should be able to deduce a polynomial.
In your case, I believe there is a reduction from 3D-MATCHING to 3PARTITION, so you would analyze that reduction to find the polynomial. Given an instance of ...
2
To complement Yuval's answer, the problem is solvable in polynomial-time more generally for block graphs which generalize complete graphs and trees. See the algorithm of Jansen [1].
On the other hand, the problem (as you probably know) remains NPC for many graphs that are close to being complete in some sense. This includes complete bipartite graphs, ...
3
Consider list coloring the complete graph, where the available colors for vertex $v$ are $L(v)$.
Form a bipartite graph in which the left-hand side corresponds to vertices and the right-hand side corresponds to colors. Connect $v$ on the left-hand side to all colors in $L(v)$ in the right-hand side.
There is a list coloring iff there is a matching ...
Top 50 recent answers are included
