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

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

Приклади

• Задача. Чи вірно, що серед чисел (-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\varphi },\ i={\sqrt {-1}},\ \varphi =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\varphi )+i\sin(k\varphi ),\ i={\sqrt {-1}},\ \varphi =2\pi /n,\ k=1..n.$
  Сертифікат. $\forall x:\cos x+{\sqrt {-1}}\sin x=e^{{\sqrt {-1}}x},$ далі див. відповідь 1.

Див. також

• свідчення (математика), an analogous concept in mathematical logic

Література

• Buhrman, Harry; Wolf, Ronald (2002), Complexity Measures and Decision Tree Complexity:A Survey.
• Computational Complexity: a Modern Approach, by Sanjeev Arora and Boaz Barak