Optimal acceptors and optimal proof systems

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

9 اقتباسات (Scopus)

ملخص

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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2010
منشور خارجيًانعم
الحدث7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010 - Prague, التشيك
المدة: ٧ يونيو ٢٠١٠١١ يونيو ٢٠١٠

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت6108 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference7th Annual Conference on Theory and Applications of Models of Computation, TAMC 2010
الدولة/الإقليمالتشيك
المدينةPrague
المدة٧/٠٦/١٠١١/٠٦/١٠

بصمة

أدرس بدقة موضوعات البحث “Optimal acceptors and optimal proof systems'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا