1
$\begingroup$

Let us assume we have a program of size $k$ that solves any instance of SAT of size $N < n$ in $poly(n)$ time. For every input of size $N \geq n$ the program is allowed not to solve it.

Then we might imagine an infinite sequence of programs of sizes $k_0 \leq k_1 \leq\ ...\ \leq k_i\leq\ ...$ which solves SAT up to the size $n_0<n_1<\ ...\ < n_i<\ ...$ in $poly(n):n<n_i$ time. And if an instance is solvable by $i^{th}$ program in $T_i(n)$ time, it's also solvable by $i+1^{th}$ program in at most $(1+1/\Omega(poly(n))T_i(n)$ time.

Also we assume the sequence is unbounded and no better sequence exists. $\forall m\in\mathbb N\ \exists i\in\mathbb N: k_i>m.$

Does the last statement mean $\mathsf{P\subsetneq NP}$? And what if we put other complexity classes and functions there?

P.S. I said time in first statement but regarding other complexity classes we might put space there too.

$\endgroup$
  • $\begingroup$ Why do you think the last statement means $\mathrm{P}\subsetneq \mathrm{NP}$? $\endgroup$ – xskxzr Apr 1 '18 at 3:44
  • $\begingroup$ @xskxzr, I'm not sure whether $P = NP$ requires a finite deterministic program that solves all instances of NP-complete problem in polynomial time. That's what I'm asking. $\endgroup$ – rus9384 Apr 1 '18 at 3:47
  • $\begingroup$ Of course, a program must be finite. To show $\mathrm{P}\subsetneq\mathrm{NP}$, you must show no program can solve any instance of SAT in polynomial time, but what does such an infinite program sequence contribute to? $\endgroup$ – xskxzr Apr 1 '18 at 4:41
  • $\begingroup$ @xskxzr, that's the thing: while there is no program that solves all instances of SAT, there can be a program that solves all real-life instances of SAT efficiently. In fact, I think, that's the way how AI is devising algorithms. $\endgroup$ – rus9384 Apr 1 '18 at 12:37
  • $\begingroup$ It makes no sense to say an algorithm solves SAT correctly on inputs of length $\le N$ in polynomial time. The running time of an algorithm is an asymptotic property, and is meaningless in regard to a finite set of inputs (unless your using a different definition of running time). For every $N$, there exists an algorithm which correctly solves sat instances of length $n<N$, and runs in constant time. Additionally, it seems that on the one hand you're looking for an upper bound (algorithm for solving sat), but on the other hand you're interested in a lower bound consequence (namely $P\neq NP$). $\endgroup$ – Ariel Apr 1 '18 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.