Shouldn't this statement be false? To be true the implication should be P=NP or am I wrong? I can't find a formal proof
6
-
1$\begingroup$ Please edit the question to include the source of the statement, i.e., where you saw it. $\endgroup$– John L.Jun 17 at 16:20
-
$\begingroup$ It is an exam question. Tell if the statement is true or false and explain why, but I can't answer even by searching on the net $\endgroup$– PatrickBatemanJun 18 at 8:12
-
$\begingroup$ I am afraid that exam question does not make sense since the best cases of SAT can be solved in $O(1)$ time. So it is not true that every algorithm that solves SAT must have complexity $\Omega(n^{\log n})$ $\endgroup$– John L.Jun 18 at 8:27
-
$\begingroup$ however the statement says if in case every algorithm that solves SAT in complexity Ω(n^(logn)), the following implication P≠NP is true?In the case of this premise, is the implication true?it does not ask whether the premise is true or false, but it does ask whether the implication is true or false given the premise, but I don't know how to answer by demonstrating the answer $\endgroup$– PatrickBatemanJun 18 at 12:33
-
$\begingroup$ If $0=1$, then P$\not=$ NP and P $=$ NP. Please take a close look. Sorry, this will be my last response. $\endgroup$– John L.Jun 18 at 13:29
|
Show 1 more comment