ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Assume the setup of the paper's fl-RDT theorem, including the quantities ψrp\psi_{rp}, ψrd\psi_{rd}, p^\hat{\mathbf p}, q^\hat{\mathbf q}, and c^\hat{\mathbf c}. Define the algorithmically achievable value ψrp,a\psi_{rp,a} by

ψrp,a=max⁡{ψrp | lim⁡n→∞P(ψrp can be achieved in polynomial time)=1}.\psi_{rp,a}=\max\left\{\psi_{rp}\ \middle|\ \lim_{n\to\infty}\mathbb{P}(\psi_{rp}\text{ can be achieved in polynomial time})=1\right\}.

Let ψrd(r)=ψrd\psi_{rd}^{(r)}=\psi_{rd}, with ψrd\psi_{rd} as in the stated fl-RDT theorem. Parametric fl-RDT algorithmic conjecture. There is an rr-sequence ψrd(r)\psi_{rd}^{(r)} with a decreasing sequence c^>\hat{\mathbf c}^{>} such that

ψrp=lim⁡r→∞ψrd(r)(p^,q^,c^>).\psi_{rp}=\lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{>} ).

If no subinterval of [0,1][0,1] contains no elements of p^\hat{\mathbf p} and q^\hat{\mathbf q}, then

ψrp=lim⁡r→∞ψrd(r)(p^,q^,c^>)=ψrp,a,SCG=ψrp−ψrp,a=0.\psi_{rp}=\lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{>} )=\psi_{rp,a},\qquad SCG=\psi_{rp}-\psi_{rp,a}=0.

Otherwise, there is an rr-sequence with an arbitrarily ordered sequence c^∼\hat{\mathbf c}^{\sim} such that

ψrd(r)(p^,q^,c^∼)≥ψrp,a,lim⁡r→∞ψrd(r)(p^,q^,c^∼)=ψ^rd=ψrp,a,\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{\sim})\geq\psi_{rp,a},\qquad \lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{\sim})=\hat{\psi}_{rd}=\psi_{rp,a},

and

SCG=ψrp−ψrp,a=lim⁡r→∞ψrd(r)(p^,q^,c^>)−lim⁡r→∞ψrd(r)(p^,q^,c^∼).SCG=\psi_{rp}-\psi_{rp,a}=\lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{>} )-\lim_{r\to\infty}\psi_{rd}^{(r)}(\hat{\mathbf p},\hat{\mathbf q},\hat{\mathbf c}^{\sim} ).

The conjecture proposes a general parametric fl-RDT mechanism relating computationally achievable values to limiting finite-parameter predictions; the source provides no resolution, so it remains open.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.