У теорії складності обчислень, сертифікат (також називається [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.
Див. також
- [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
Це незавершена стаття про інформаційні технології. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi skladnosti obchislen sertifikat takozh nazivayetsya en pevnoyi zadachi ce ryadok yakij pidtverdzhuye zasvidchuye sertifikuye rozv yazok ciyeyi zadachi test yakij pereviryaye vidpovid na cyu zadachu Prikladi Zadacha Chi virno sho sered chisel 2 3 15 14 7 10 ye taki sho yihnya suma dorivnyuye 0 Vidpovid tak Sertifikat 2 3 15 10 0 Zadacha Skilki isnuye variantiv rozkladennya chisla 5 displaystyle 5 u sumu naturalnih chisel Vidpovid 7 displaystyle 7 variantiv Sertifikat 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 Zadacha Znajti koreni rivnyannya x n 1 displaystyle x n 1 Vidpovid 1 x k e k i f i 1 f 2 p n k 1 n displaystyle x k e ki varphi i sqrt 1 varphi 2 pi n k 1 n Sertifikat Vidomo sho e 2 p 1 1 displaystyle e 2 pi sqrt 1 1 otzhe x k n e k 2 p 1 1 displaystyle x k n e k2 pi sqrt 1 1 Vidpovid 2 x k cos k f i sin k f i 1 f 2 p n k 1 n displaystyle x k cos k varphi i sin k varphi i sqrt 1 varphi 2 pi n k 1 n Sertifikat x cos x 1 sin x e 1 x displaystyle forall x cos x sqrt 1 sin x e sqrt 1 x dali div vidpovid 1 Div takozh en an analogous concept in mathematical logicLiteraturaBuhrman Harry Wolf Ronald 2002 Complexity Measures and Decision Tree Complexity A Survey Computational Complexity a Modern Approach by Sanjeev Arora and Boaz Barak Ce nezavershena stattya pro informacijni tehnologiyi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi