0
$\begingroup$

Let $X=P$, then we can have function

L = len(input)
k = 0
while (L>0):
    k = k+1
    L = log2(L)
if (k mod 4 == c):
    for 2^len(input):
        pass
return 1

which, for every $n$, we have a $c\in \{0,1,2,3\}$, making all inputs shorter than $n$ runs in $Poly(n)$ time; but no matter what $c$ is, it doesn't run in polynomial time. Yet, let $X=R$, then proof that finding is possible is shown here.

Note that function

return 1

always return the same value and is polynomial time, but we require to select one rather than create one program. Proof that creating is possible is shown here.

So what should $X$ be so that, if solver needs to consider smaller inputs, at least one of the limit(s) of $X/O(1)$ solve problem in $X$? What should $X$ be so that, All of the limit(s) of $X/O(1)$ solve problem in $X$?

$\endgroup$
  • $\begingroup$ What's $X$? What do you mean by $X=P$ or $X=R$? What's $X$ and what's $R$? What do you mean by "proof that finding is possible"? What do you mean by "the solver"? What is $X/O(1)$, and what is meant by "its limits"? Can you edit the question to clarify and define all notation in a self-contained way? $\endgroup$ – D.W. Dec 25 '19 at 17:43

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.