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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

У теорії складності обчислень, сертифікат (також називається свідченням[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.

Див. також[ред.ред. код]

Література[ред.ред. код]