[id20926|Интерактивные доказательства]
Санкт-Петербург / весна 2019 / 23 марта, CS клуб
Даниил Владимирович Мусатов
Обычно под доказательством понимают некоторый текст, убеждающий читателя в справедливости некоторого утверждения. В математике подразумевается, что доказательство проверяется алгоритмически и может иметь вид цепочки формул некоторой логической системы, либо быть более общим. Например, предъявление решения головоломки доказывает, что решение существует. Если алгоритм проверки доказательства работает за полиномиальное время, то задача определения истинности относится к классу NP. Если рассмотреть вероятностные алгоритмы проверки, получится чуть более широкий класс MA. Это самый широкий класс, для которого есть "публикуемые доказательства", которые можно эффективно проверить без участия автора.
В теории интерактивных доказательств [id87557132|концепция полностью меняется]. Теперь доказательство это не текст, а диалог, как на устном экзамене или докладе на научном семинаре. [id81102|Участники диалога - прувер], стремящийся доказать некоторое утверждение, и верификатор, который должен проверить корректность. Прувер должен суметь доказать любое верное утверждение и не должен доказать никакое неверное (с высокой вероятностью). При этом прувер [id115343|никак вычислительно не ограничен], а верификатор должен использовать только полиномиальные вероятностные вычисления. Класс [id31609798|доказуемых в этом смысле утверждений называется IP], мини-курс будет посвящён изучению этого класса и его вариаций. На первых двух лекциях мы изучим базовую теорию и докажем теорему IP=PSPACE. На следующих двух лекциях мы познакомимся с [id42069|теорией доказательств с несколькими пруверами] и новым подходом - теорией рациональных интерактивных доказательств.
https://compsciclub.ru/courses/interactive-proofs/2019-spring/
Санкт-Петербург / весна 2019 / 23 марта, CS клуб
Даниил Владимирович Мусатов
Обычно под доказательством понимают некоторый текст, убеждающий читателя в справедливости некоторого утверждения. В математике подразумевается, что доказательство проверяется алгоритмически и может иметь вид цепочки формул некоторой логической системы, либо быть более общим. Например, предъявление решения головоломки доказывает, что решение существует. Если алгоритм проверки доказательства работает за полиномиальное время, то задача определения истинности относится к классу NP. Если рассмотреть вероятностные алгоритмы проверки, получится чуть более широкий класс MA. Это самый широкий класс, для которого есть "публикуемые доказательства", которые можно эффективно проверить без участия автора.
В теории интерактивных доказательств [id87557132|концепция полностью меняется]. Теперь доказательство это не текст, а диалог, как на устном экзамене или докладе на научном семинаре. [id81102|Участники диалога - прувер], стремящийся доказать некоторое утверждение, и верификатор, который должен проверить корректность. Прувер должен суметь доказать любое верное утверждение и не должен доказать никакое неверное (с высокой вероятностью). При этом прувер [id115343|никак вычислительно не ограничен], а верификатор должен использовать только полиномиальные вероятностные вычисления. Класс [id31609798|доказуемых в этом смысле утверждений называется IP], мини-курс будет посвящён изучению этого класса и его вариаций. На первых двух лекциях мы изучим базовую теорию и докажем теорему IP=PSPACE. На следующих двух лекциях мы познакомимся с [id42069|теорией доказательств с несколькими пруверами] и новым подходом - теорией рациональных интерактивных доказательств.
https://compsciclub.ru/courses/interactive-proofs/2019-spring/
[id20926 | Interactive evidence]
St. Petersburg / spring 2019 / March 23, CS club
Daniil Vladimirovich Musatov
Usually, proof is understood as some text convincing the reader of the validity of some statement. In mathematics, it is understood that the proof is verified algorithmically and can take the form of a chain of formulas of some logical system, or be more general. For example, presenting a puzzle solution proves that a solution exists. If the proof verification algorithm works in polynomial time, then the truth determination problem belongs to the class NP. If we consider probabilistic verification algorithms, we get a slightly wider class MA. This is the widest class for which there is “published evidence” that can be effectively verified without the participation of the author.
In the theory of interactive evidence [id87557132 | the concept is completely changing]. Now proof is not a text, but a dialogue, as in an oral exam or a report at a scientific seminar. [id81102 | Participants in the dialogue - prover], seeking to prove a statement, and a verifier that must verify the correctness. The prover must be able to prove any true statement and must not prove any false (with high probability). Moreover, the prover [id115343 | is not computationally limited in any way], and the verifier should use only polynomial probabilistic calculations. The class [id31609798 | statements proved in this sense is called IP], a mini-course will be devoted to the study of this class and its variations. In the first two lectures, we will study the basic theory and prove the theorem IP = PSPACE. In the next two lectures, we will introduce [id42069 | a theory of evidence with several provers] and a new approach - the theory of rational interactive evidence.
https://compsciclub.ru/courses/interactive-proofs/2019-spring/
St. Petersburg / spring 2019 / March 23, CS club
Daniil Vladimirovich Musatov
Usually, proof is understood as some text convincing the reader of the validity of some statement. In mathematics, it is understood that the proof is verified algorithmically and can take the form of a chain of formulas of some logical system, or be more general. For example, presenting a puzzle solution proves that a solution exists. If the proof verification algorithm works in polynomial time, then the truth determination problem belongs to the class NP. If we consider probabilistic verification algorithms, we get a slightly wider class MA. This is the widest class for which there is “published evidence” that can be effectively verified without the participation of the author.
In the theory of interactive evidence [id87557132 | the concept is completely changing]. Now proof is not a text, but a dialogue, as in an oral exam or a report at a scientific seminar. [id81102 | Participants in the dialogue - prover], seeking to prove a statement, and a verifier that must verify the correctness. The prover must be able to prove any true statement and must not prove any false (with high probability). Moreover, the prover [id115343 | is not computationally limited in any way], and the verifier should use only polynomial probabilistic calculations. The class [id31609798 | statements proved in this sense is called IP], a mini-course will be devoted to the study of this class and its variations. In the first two lectures, we will study the basic theory and prove the theorem IP = PSPACE. In the next two lectures, we will introduce [id42069 | a theory of evidence with several provers] and a new approach - the theory of rational interactive evidence.
https://compsciclub.ru/courses/interactive-proofs/2019-spring/
У записи 1 лайков,
0 репостов,
264 просмотров.
0 репостов,
264 просмотров.
Эту запись оставил(а) на своей стене Наима Джошуа
