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

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

Приклади
  • Задача. Чи вірно, що серед чисел (-2, -3, 15, 14, 7, -10, …) є такі, що їхня сума дорівнює 0?
    Відповідь: так. Сертифікат. -2 -3 + 15 -10 = 0.
  • Задача. Скільки існує варіантів розкладення числа у суму натуральних чисел.
    Відповідь: варіантів. Сертифікат: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1.
  • Задача. Знайти корені рівняння
    Відповідь 1.
    Сертифікат. Відомо, що , отже,
    Відповідь 2.
    Сертифікат. далі див. відповідь 1.

Див. також

ред.

Література

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