# $p\; ?=\; NP$ --- ## **terms** ---- ### ***quickly*** - For convenience, we unoffically define a term ***quickly*** - If we say a problem or a task run *quickly*, **means the existence of an algorithm solving the task that runs in polynomial time** - Such that the time to complete the task varies as a polynomial function on the **size of the input** to the algorithm ---- ### **P(P Problem)** - The general class of questions for which some algorithm can provide an answer ***quickly*** is "P" ---- ### **NP(non-deterministic P Problem)** - The general class of questions for which some algorithm can **not** provide an answer ***quickly*** is "NP" ---- ### **verify answer** - An answer to the P and NP question can both be solved ***quickly*** ---- ### **time complexity**  ~~By Foxconn Specialist~~ <font size=6> - The time complexity is generally expressed as a function of the size of the input. - We only focus on the behavior of the complexity when the input size increases — **asymptotic behavior** - Therefore, the time complexity is commonly expressed using big O notation, typically $O(n),\;O(n\log n),\;O(n^\alpha),\;O(2^n)$ </font> ---- ### **asymptotic behavior** - Formally, given function $f(x)$ and $g(x)$, we define a binary relation $$f(x)\sim g(x) \;\; (as\;x \to \infty) \Leftrightarrow \lim_{x\to \infty}\frac{f(x)}{g(x)}\in R$$ ---- ### **asymptotic analysis on big-O** - For a task running time with $n$ input size, $f(n)$, consider a function $g(n)$ : $$ \lim_{n\to \infty}\frac{f(n)}{g(n)}\in R$$ - Obviously, $g(n)$ is a set. So we use $g(n)$ to represent the maximal element. - $O(g(n))$ is complexity of that task running time --- ## “Does P equal NP?” means “If the solution to a problem can be verified in polynomial time, can it be found in polynomial time? --- ## **conclusion** ---- ### **author's opinion** - If we want to calculate the subset number of a $n$ size set in naïve way, the time is $O(2^n)$ ---- ### **author's optimization** - $$\begin{bmatrix} L & E \\ I & T \end{bmatrix}$$ - $$T(n) = (E:2-(E:2:(sbasis:(I-L))))∙sbasis$$ ---- #### $$T(n) = (E:2-(E:2:(sbasis:(I-L))))∙sbasis$$ - The complexity of this magically emerge$$T(n)=T(\frac{n}{2})+O(1)$$ ---- ### $$T(n)=T(\frac{n}{2})+O(1)$$ - According to the Master Theorem **case 1** - $\because \exists\;\epsilon >0\;s.t.\;f(n)=O(1)=O(n^{(\log_{2}1)-\epsilon})\\\therefore T(n)=\Theta(n^{\log_{2}1})=O(\log_2 n)$ ---- ### Master Theorem **case 1** proof - Consider a function $T(n) = aT(\frac{n}{b})+f(n)$ - Without loss of generality, let $f(n)=n^d$ - So we can get $T(n) = aT(\frac{n}{b})+n^d$, $a\geq 1,\;b>1,\;d\geq0$ ---- #### $T(n) = aT(\frac{n}{b})+n^d$, $a\geq 1,\;b>1,\;d\geq0$ <font size=6> - consider the recursive relation - for $0^{th}$ layer cost $n^d$ to merge - for $1^{st}$ layer cost $O(a*(\frac{n}{b})^d)$ to merge, that is $\frac{a}{b^d}*n^d$ - for $2^{nd}$ layer cost $O(a^2*(\frac{n}{b^2})^d)$ to merge, that is $(\frac{a}{b^d})^2*n^d$ - $k^{th}$ layer cost $O(a^k*(\frac{n}{b^k})^d)$ to merge, that is $(\frac{a}{b^d})^k*n^d$ </font> ---- ### $k^{th}$ layer cost $(\frac{a}{b^d})^k*n^d$ \begin{split} \therefore T(n) &= \sum_{i=0}^{k}((\frac{a}{b^d})^i*n^d)=n^d*\sum_{i=0}^{k}(\frac{a}{b^d})^i\\ &= n^k*\frac{1-(\frac{a}{b^d})^{k+1}}{1-(\frac{a}{b^d})} \end{split} ---- ### $T(n)=n^k*\frac{1-(\frac{a}{b^d})^{k+1}}{1-(\frac{a}{b^d})}$ - for $T(n)=T(\frac{n}{2})+O(1)$ and $aT(\frac{n}{b})+n^d$ - obviously, $a = 1,\;b = 2,\;d = 0$ - therefore $\frac{a}{b^d}=1$ - if we use the formula above directly, it occurr some error ---- ### $T(n)=n^k*\frac{1-(\frac{a}{b^d})^{k+1}}{1-(\frac{a}{b^d})}$ broken ?!! ---- ### $$T(n) = n^d*\sum_{i=0}^{k}(\frac{a}{b^d})^i,\;hahaha!!$$ $\because a = 1,\;b = 2,\;d = 0\\\therefore T(n)=n^0*k,\;$ ---- ### $T(n)=n^0*k$ - $n$ is divided by $b$ on every layer $\therefore k = \log_b n\\\because a = 1,\;b = 2,\;d = 0\\\therefore T(n) = \Theta(\log_2 n)=O(\log_2 n)$ --- # $T(n)=O(\log_2 n)$