Сертифікат (складність обчислень)

У теорії складності обчислень, сертифікат (також називається Шаблон:Iw2) певної задачі — це рядок, який підтверджує (засвідчує, сертифікує) розв'язок цієї задачі; тест, який перевіряє відповідь на цю задачу.

Приклади

• Задача. Чи вірно, що серед чисел (-2, -3, 15, 14, 7, -10, …) є такі, що їхня сума дорівнює 0?
  Відповідь: так. Сертифікат. -2 -3 + 15 -10 = 0.
• Задача. Скільки існує варіантів розкладення числа $5$ у суму натуральних чисел.
  Відповідь: $7$ варіантів. Сертифікат: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1.
• Задача. Знайти корені рівняння $x^n=1.$
  Відповідь 1. $x_k=e^{ki\phi },i=\sqrt{-1},\phi =2\pi /n,k=1..n.$
  Сертифікат. Відомо, що $e^{2\pi \sqrt{-1}}=1$, отже, $x_k^n=e^{k2\pi \sqrt{-1}}=1$
  Відповідь 2. $x_k=\cos (k\phi )+i\sin (k\phi ),i=\sqrt{-1},\phi =2\pi /n,k=1..n.$
  Сертифікат. $\mathrm{\forall }x:\cos x+\sqrt{-1}\sin x=e^{\sqrt{-1}x},$ далі див. відповідь 1.

Див. також

• Шаблон:Iw2, an analogous concept in mathematical logic

Література

• Шаблон:Citation.
• Computational Complexity: a Modern Approach, by Sanjeev Arora and Boaz Barak