New answers tagged

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
1 vote

What does O( n^{1+o(1)} ) mean

As n grows, o(1) eventually becomes less than 1, then less than 1/2, then less than 1/3 and so on. So as n gets large, f(n) will be O(n ^ 3/2), O(n ^ 4/3) and so on. The factor between n and f(n) can ...
user avatar
  • 25.2k
3 votes
Accepted

What does O( n^{1+o(1)} ) mean

A function $f(n)$ is $O(n^{1+o(1)})$ if there exist a constant $C > 0$ and a function $g(n)$ satisfying $\lim_{n\to\infty} g(n) = 0$ such that $$ f(n) \leq Cn^{1+g(n)}. $$
user avatar
4 votes
Accepted

Complexity of the (Complete/Assign) 3-SAT problem?

Let $C_1 \lor \cdots \lor C_m$ be a 3CNF. We replace the clause $C_i = \ell_1 \lor \ell_2 \lor \ell_3$ with the clause $C'_i = \ell_1^{(i)} \lor \ell_2^{(i)} \lor \ell_3^{(i)}$, that is, with a clause ...
user avatar

Top 50 recent answers are included