New answers tagged

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 $\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
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 \...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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)$)...
user avatar
  • 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+...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
  • 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. ...
user avatar
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$ ...
user avatar
  • 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}}$, ...
user avatar
  • 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 ...
user avatar
  • 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(...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 18.9k
0 votes

Complexity of T(n)=2T(n-1)

A sum of $m$ constants takes time $O(m)$.
user avatar
  • 3,912
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| ...
user avatar

Top 50 recent answers are included