New answers tagged complexity-theory
2
votes
MSAT and IMSAT problems (restricted versions of SAT)
For your first question, I'll give an elementary proof for the $\mathsf{NP}$-hardness of $\mathrm{MSAT}$ by reduction from $\mathrm{SAT}$.
Let $\varphi$ be a propositional formula in CNF (i.e., a $\...
- 1,331
0
votes
Accepted
Do uncomputable functions exist that are of the order of a computable function?
Yes. Let $L$ be any undecidable language (e.g. the halting problem), w.l.o.g. encoded over the alphabet $\{0, 1\}$ and such that all $x \in L$ start with $1$. Further, let $\leq_\text{lex}$ denote the ...
- 1,331
0
votes
Accepted
Is there a minimal order of an uncomputable function that bounds all computable functions?
Suppose that $h$ is such that $g = O(h)$ for all computable $g$. Let $H(n) = h(n)/n$. I claim that $H$ also satisfies $g = O(H)$ for all computable $g$. Otherwise, let $g$ be a computable function ...
- 270k
0
votes
Accepted
Is there a maximal order of computable functions?
Suppose that such a computable function $f$ exists. The function $h(n) = nf(n) + n$ is also computable, but $h(n)$ is not $O(f(n))$.
We can similarly rule out a uniformly computable countable order, ...
- 270k
1
vote
Number of equivalence classes in $P$
The existing answer is good, but doesn't tackle the empty and full languages and also leaves some doubts unspecified. I'll solve the full question.
First, let's be clear about our definitions: $L_1 \...
- 111
5
votes
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
Big-O notation can be tricky because it hides details. Big-O describes a way to measure a function related to complexity. That function may be "number of memory accesses," which would ...
- 3,085
2
votes
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
The cost of array access would be for example $c_1$ if the array size is less than $2^{64}$, $c_2$ if the array size is less than $2^{128}$, $c_3$ if the array size is less than $2^{256}$ and so on. ...
- 25.2k
31
votes
Accepted
Array access is O(1) implies a fixed index size, which implies O(1) array traversal?
It's a good question. From a pragmatic perspective, we tend not to worry about it.
From a theoretical perspective, see the transdichotomous model. In particular, a standard assumption is that there ...
D.W.♦
- 141k
1
vote
Accepted
Simulating nondeterministic RAM with nondeterminstic turing machine
Here is your hint. Imagine that we augment $P$ to record a log of all the random-access reads and writes $P$ does to memory (i.e., for each read, record the address and the value that was read; for ...
D.W.♦
- 141k
0
votes
Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?
Intuitively : Number of nodes in last level is more than sum of all nodes in Previous level.
At Level-$\color\red0$, we have $1$ node. It can be written as $b^\color\red0$
At Level-$\color\red1$, we ...
- 231
0
votes
Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?
Hint:
$$s(d):=b^0+b^1+b^2+\cdots b^d=\frac{b^{d+1}-1}{b-1}$$
and by summation until $d+1$ and differentiation,
$$t(d):=0b^0+1b^1+2b^2+\cdots db^d=\frac{\partial}{\partial b}s(d+1)=\frac{d b^{d+1} - (1 ...
- 3,912
0
votes
Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?
Let x = $b^d$. The last term is x. The second to last is x * (2 / b). The third to last is $x * (3 / b^2)$, then $x * (4 / b^3)$ etc.
Let y = $x * (1 + 1 / b + 1 / b^2 + 1 / b^3 ...)$. That's a simple ...
- 25.2k
0
votes
Accepted
Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?
If $b, d$ goes to infinity, as all other sum factors are asymptotically less than $b^d$ (except the last one!), the mentioned time complexity function will be in $\Theta(b^d)$. Hence, this algorithm ...
- 3,512
4
votes
Accepted
Turing Machines time complexity with regard to the NP and P problem
What are the 'advantages' of a deterministic TM over the non-deterministic one?
The advantage of the deterministic TM is that deterministic Turing Machines represent the type of computation we are ...
- 1,055
1
vote
Big O notation simplification from sum
If you multiply $m$ by $10$, the magnitude of the term varies by a factor
$$\sqrt{\frac{n+10m}{n+m}}=\sqrt{\frac{\frac nm+10}{\frac nm+1}}.$$
That factor stays in range $\left(1,\sqrt{10}\right)$ and ...
- 3,912
1
vote
Big O notation simplification from sum
Presumably you are after a substitution like$$\sqrt{n+m}\,n^3\le f(n)\,g(m),$$ or equivalently
$$n+m\le p(n)\,q(m).$$
If you freeze $m$, then $p(n)=\Omega(n)$ must hold (and similarly $q(m)=\Omega(m)$)...
- 3,912
0
votes
Big O notation simplification from sum
Assume $O(\sqrt{n+m}~n^3)$ is considered as an upper bound when $n$ and $m$ go to infinity.
There is an obvious replacement, $O(m^{1/2}n^{7/2})$, which is, however, not satisfactory as $\frac{\sqrt{n+...
- 34.1k
0
votes
Can you help me find some examples of 3co-SAT for 4 variables?
CNF is only used to describe problem formally, but it's kind of hard for human to understand it. Entailment is such tool that used to write "readable" formula. You can use propositional ...
- 93
1
vote
Accepted
What is different between two classes are 'incomparable' or two classes are 'not equal'?
Two sets $A$ and $B$ are comparable if $A \subseteq B$ or $B \subseteq A$. However, if $A \neq B$, it could be that $A \subsetneq B$ or $B \subsetneq A$.
If $A \neq B$ and $A$ and $B$ are comparable, ...
- 13.3k
0
votes
Reducing euclidean TSP of smaller size to euclidean TSP of bigger size
If you need a mathematical guarantee, you should run $k-1$ times the $N$-solver algorithm. In other words, repeat the following approach for each vertex $v_i\ \ i=2,...,k$ and take the best solution.
...
3
votes
Can almost equal partition problem be solved in polynomial time?
Yes, this problem is polynomial-time solvable.
Let $A$ be the input numbers and let $S = \mathrm{sum}(A)$ be its sum.
Let $T_1 = 0.49S$, $T_2 = 0.51 S$ be the target sum range. Let $\epsilon = 0.02$ ...
- 826
3
votes
Accepted
Is this special case of the subset-product problem $\mathsf{NP}$-complete?
Yes, your problem is NP-complete, even when we restrict to the case where $t=1$.
We will focus on the case $M=2^k$. Then $\mathbb{Z}_M^*$ is isomorphic to $\mathbb{Z}_2 \times \mathbb{Z}^{2^{k-2}}$, ...
D.W.♦
- 141k
4
votes
Accepted
The optimal complexity of intersecting a line with a convex hull of a set of points in 2d
What you're asking for reduces to finding the so-called bridges of the convex hull across this line, i.e. the two edges of the convex hull which have one vertex on both sides of the line. Kirkpatrick ...
- 2,209
0
votes
The optimal complexity of intersecting a line with a convex hull of a set of points in 2d
I think it can be done in O(N).
WLOG, we assume the line is $x=0$, and the intersection set is non empty. We can rotate the point set if the line is not $x=0$. The intersection check can be done in O(...
2
votes
The class of problems that can be solved efficiently using physical means?
No one knows. The extended Church-Turing hypothesis is sometimes described as saying that the answer is Phys-P = BPP. This is a conjecture or hypothesis but it is not proven. The answer depends on ...
D.W.♦
- 141k
3
votes
The class of problems that can be solved efficiently using physical means?
It's not clear what "can be solved" actually means here. Let me explain with a real example.
It is known that NP-hard problems can be solved on an analog computer in polynomial time.
Suppose ...
- 18.9k
0
votes
2
votes
Accepted
Why can't you randomize an advice string to show that $P/poly \subseteq NP$
Consider the following functions with advice:
$$ f(a,x) = a. $$
(The advice $a$ is one bit.)
The function $f$ is computable in polynomial time, and this shows that any language of the form $\{ x : |x| ...
- 270k
Top 50 recent answers are included