Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Unless we resolve the P vs NP question, we are unable to say whether there is an algorithm (acceptor) that accepts Boolean tautologies in polynomial time and does not accept non-tautologies (with no time restriction). Unless we resolve the co-NP vs NP question, we are unable to say whether there is a proof system that has a polynomial-size proof for every tautology. In such a situation, it is typical for complexity theorists to search for "universal" objects; here, it could be the "fastest" acceptor (called optimal acceptor) and a proof system that has the "shortest" proof (called optimal proof system) for every tautology. Neither of these objects is known to the date. In this survey we review the connections between these questions and generalizations of acceptors and proof systems that lead or may lead to universal objects.
Язык оригинала | английский |
---|---|
Название основной публикации | Theory and Applications of Models of Computation - 7th Annual Conference, TAMC 2010, Proceedings |
Страницы | 28-39 |
Число страниц | 12 |
DOI | |
Состояние | Опубликовано - 15 июл 2010 |
Событие | 7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010 - Prague, Чехия Продолжительность: 7 июн 2010 → 11 июн 2010 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 6108 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010 |
---|---|
Страна/Tерритория | Чехия |
Город | Prague |
Период | 7/06/10 → 11/06/10 |
ID: 49827737