ترغب بنشر مسار تعليمي؟ اضغط هنا

Relativization of Gurevichs Conjectures

62   0   0.0 ( 0 )
 نشر من قبل Anatole Dahan
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Gurevich (1988) conjectured that there is no logic for $textsf{P}$ or for $textsf{NP}cap textsf{coNP}$. For the latter complexity class, he also showed that the existence of a logic would imply that $textsf{NP} cap textsf{coNP}$ has a complete problem under polynomial time reductions. We show that there is an oracle with respect to which $textsf P$ does have a logic and $textsf P etextsf{NP}$. We also show that a logic for $textsf{NP} cap textsf{coNP}$ follows from the existence of a complete problem and a further assumption about canonical labelling. For intersection classes $Sigma^p_n cap Pi^p_n$ higher in the polynomial hierarchy, the existence of a logic is equivalent to the existence of complete problems.



قيم البحث

اقرأ أيضاً

104 - Moa Johansson 2021
A key component of mathematical reasoning is the ability to formulate interesting conjectures about a problem domain at hand. In this paper, we give a brief overview of a theory exploration system called QuickSpec, which is able to automatically disc over interesting conjectures about a given set of functions. QuickSpec works by interleaving term generation with random testing to form candidate conjectures. This is made tractable by starting from small sizes and ensuring that only terms that are irreducible with respect to already discovered conjectures are considered. QuickSpec has been successfully applied to generate lemmas for automated inductive theorem proving as well as to generate specifications of functional programs. We give an overview of typical use-cases of QuickSpec, as well as demonstrating how to easily connect it to a theorem prover of the users choice.
158 - Olivier Finkel 2012
An {omega}-language is a set of infinite words over a finite alphabet X. We consider the class of recursive {omega}-languages, i.e. the class of {omega}-languages accepted by Turing machines with a Buchi acceptance condition, which is also the class {Sigma}11 of (effective) analytic subsets of X{omega} for some finite alphabet X. We investigate here the notion of ambiguity for recursive {omega}-languages with regard to acceptance by Buchi Turing machines. We first present in detail essentials on the literature on {omega}-languages accepted by Turing Machines. Then we give a complete and broad view on the notion of ambiguity and unambiguity of Buchi Turing machines and of the {omega}-languages they accept. To obtain our new results, we make use of results and methods of effective descriptive set theory.
We present polygraphic programs, a subclass of Albert Burronis polygraphs, as a computational model, showing how these objects can be seen as first-order functional programs. We prove that the model is Turing complete. We use polygraphic interpretati ons, a termination proof method introduced by the second author, to characterize polygraphic programs that compute in polynomial time. We conclude with a characterization of polynomial time functions and non-deterministic polynomial time functions.
116 - Olivier Finkel 2008
We prove in this paper that the length of the Wadge hierarchy of omega context free languages is greater than the Cantor ordinal epsilon_omega, which is the omega-th fixed point of the ordinal exponentiation of base omega. The same result holds for t he conciliating Wadge hierarchy, defined by J. Duparc, of infinitary context free languages, studied by D. Beauquier. We show also that there exist some omega context free languages which are Sigma^0_omega-complete Borel sets, improving previous results on omega context free languages and the Borel hierarchy.
We show that there are $Sigma_3^0$-complete languages of infinite words accepted by non-deterministic Petri nets with Buchi acceptance condition, or equivalently by Buchi blind counter automata. This shows that omega-languages accepted by non-determi nistic Petri nets are topologically more complex than those accepted by deterministic Petri nets.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا