كود قابل للاختبار محليًا

يُعدّ الرمز القابل للاختبار محليًا نوعًا من رموز تصحيح الأخطاء، حيث يُمكن تحديد ما إذا كانت سلسلة نصية ما كلمةً في هذا الرمز من خلال فحص عدد صغير (غالبًا ثابت) من بتات السلسلة. في بعض الحالات، يكون من المفيد معرفة ما إذا كانت البيانات تالفة دون فك تشفيرها بالكامل، لاتخاذ الإجراء المناسب. على سبيل المثال، في مجال الاتصالات، إذا واجه المُستقبِل رمزًا تالفًا، يُمكنه طلب إعادة إرسال البيانات، مما قد يزيد من دقتها. وبالمثل، في مجال تخزين البيانات، تُتيح هذه الرموز استعادة البيانات التالفة وإعادة كتابتها بشكل صحيح.

في المقابل، تستخدم الرموز القابلة للفك محليًا عددًا قليلًا من بتات كلمة الرمز لاستعادة المعلومات الأصلية احتماليًا . ويحدد معدل الأخطاء مدى احتمالية استعادة المُفكِّك للبت الأصلي بشكل صحيح؛ ومع ذلك، لا يمكن اختبار جميع الرموز القابلة للفك محليًا محليًا. ^{[ 1 ]}

من الواضح أنه ينبغي قبول أي كلمة رمزية صحيحة، لكن السلاسل النصية التي لا تُعدّ كلمات رمزية قد تختلف بتًا واحدًا فقط، مما يستلزم إجراء العديد من عمليات التحقق (أكثر من عدد ثابت بالتأكيد). ولمعالجة هذا الأمر، يُعرَّف فشل الاختبار فقط إذا كانت السلسلة النصية مختلفة بنسبة محددة على الأقل من بتاتها. وهذا يعني أن كلمات الشفرة يجب أن تكون أطول من سلاسل الإدخال بإضافة بعض التكرار.

تُستخدم مسافة هامينغ لقياس المسافة بين وترين.

${\displaystyle \Delta (x,y)=|\{i:x_{i}\neq y_{i}\}|}$

مسافة الخيط${\displaystyle w}$من رمز${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$يتم حسابها بواسطة

${\displaystyle \Delta (w,C)=\min _{x}\{\Delta (w,C(x))\}}$

يتم حساب المسافات النسبية كجزء من عدد البتات.

${\displaystyle \delta (x,y)=\Delta (x,y)/n{\text{ و }}\delta (w,C)=\Delta (w,C)/n}$

رمز${\displaystyle C:\{0,1\}^{k}\to \{0,1\}^{n}}$يُطلق عليه اسم${\displaystyle q}$-محلي${\displaystyle \delta }$- قابل للاختبار ما إذا كانت هناك آلة تورينج M مع إمكانية الوصول العشوائي إلى مدخل${\displaystyle w}$هذا يجعل الأمر على الأكثر${\displaystyle q}$الاستعلامات غير التكيفية لـ${\displaystyle w}$ويستوفي الشروط التالية: ^{[ 2 ]}

• لأي${\displaystyle x\in \{0,1\}^{k}}$و${\displaystyle w=C(x)}$،${\displaystyle العلاقات العامة[M^{w}(1^{k})=1]=1}$بمعنى آخر، يقبل M الوصول الممنوح لأي كلمة رمزية لـ C.
• ل${\displaystyle w\in \{0,1\}^{n}}$بحيث${\displaystyle \delta (w,C)>\delta }$،${\displaystyle Pr[M^{w}(1^{k})=1]\leq 1/2}$يجب على M رفض السلاسل${\displaystyle \delta }$-بعيداً عن ج على الأقل نصف الوقت.

كما أن معدل الشفرة هو النسبة بين طول الرسالة وطول كلمة الشفرة

${\displaystyle r={\frac {|x|}{|C(x)|}}}$

يبقى السؤال مفتوحًا حول ما إذا كانت هناك أي رموز قابلة للاختبار محليًا ذات حجم خطي، ولكن هناك العديد من التركيبات التي تعتبر "خطية تقريبًا": ^{[ 3 ]}

1. متعددة الحدود قريبة بشكل تعسفي من الخطية؛ لأي${\displaystyle \epsilon >0}$،${\displaystyle n=k^{1+\epsilon }}$.
2. دوال من الشكل${\displaystyle n=k^{1+\epsilon (k)}}$، أين${\displaystyle \epsilon (k)}$هي دالة تقترب من الصفر. وهذا يجعل n أقرب إلى الخطية مع ازدياد k. على سبيل المثال:
   • ${\displaystyle 1/\log \log k}$
   • ${\displaystyle 1/(\log k)^{c}}$بالنسبة للبعض${\displaystyle c\in (0,1)}$
   • ${\displaystyle \exp((\log \log \log k)^{c})/\log k}$ل${\displaystyle c\in (0,1)}$

وقد تحققت هذه الأهداف جميعها، حتى مع ثبات تعقيد الاستعلام واستخدام الأبجدية الثنائية ، كما هو الحال مع${\displaystyle n=k^{1+1/(\log k)^{c}}}$لأي${\displaystyle c\in (0,1)}$. الهدف التالي شبه الخطي هو خطي حتى عامل متعدد اللوغاريتمات ؛${\displaystyle n={\text{poly}}(\log k)*k}$لم يتوصل أحد حتى الآن إلى كود قابل للاختبار بشكل خطي يفي بهذا القيد. ^{[ 3 ]}

في نوفمبر 2021، نشرت ورقتان بحثيتان ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ]} أول بناء زمني متعدد الحدود لـ "${\displaystyle c^{3}}$-LTCs" أي الأكواد القابلة للاختبار محليًا بمعدل ثابت${\displaystyle r}$مسافة ثابتة${\displaystyle \delta }$وموقع ثابت${\displaystyle q}$.

تتشابه الشفرات القابلة للاختبار محليًا إلى حد كبير مع البراهين القابلة للتحقق احتماليًا . ويتضح ذلك من أوجه التشابه في بنيتها. ففي كليهما، لدينا${\displaystyle q}$يتم إدخال استعلامات عشوائية غير تكيفية في سلسلة نصية كبيرة، وإذا أردنا قبولها، فيجب علينا ذلك باحتمالية 1، وإذا لم نرغب في ذلك، فيجب ألا نقبلها إلا في نصف الحالات على الأكثر. والفرق الرئيسي هو أن بروتوكولات معالجة الطلبات (PCPs) مهتمة بالقبول.${\displaystyle x}$إذا كان هناك${\displaystyle w}$لهذا السبب.${\displaystyle M^{w}(x)=1}$أما الأكواد القابلة للاختبار محليًا، من ناحية أخرى، فتقبل${\displaystyle w}$إذا كان جزءًا من الكود. قد تحدث العديد من المشاكل عند افتراض أن برهان PCP يُشفّر كودًا قابلًا للاختبار محليًا. على سبيل المثال، لا يُشير تعريف PCP إلى البراهين غير الصالحة، بل إلى المدخلات غير الصالحة فقط.

على الرغم من هذا الاختلاف، فإن الشفرات القابلة للاختبار محليًا ووحدات التحقق من صحة البرامج (PCPs) متشابهة بما يكفي بحيث أنه في كثير من الأحيان، عند إنشاء إحداها، يقوم المُثبت بإنشاء الأخرى أثناء العملية. ^{[ 8 ]}

• متجه جيلبرت-فارشاموف
• شفرة هامينغ
• رمز الموسع

• "الاختراقات - أكواد قابلة للاختبار محليًا بمعدل ثابت، ومسافة ثابتة، وموقع ثابت | معهد سيمونز لنظرية الحوسبة" . simons.berkeley.edu . 6 أكتوبر 2021.