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

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

Приклади

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

Див. також

• ^[en], 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