𝔖 Bobbio Scriptorium
✦   LIBER   ✦

More on the complexity of slice functions

✍ Scribed by Ingo Wegener

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
664 KB
Volume
43
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Bounding the Complexity of Advice Functi
Bounding the Complexity of Advice Functions
✍ R. Gavalda πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 624 KB

It was known that every set \(\boldsymbol{A}\) in \(P\) poly has an advice function in \(\operatorname{PF}\left(\Sigma_{2}^{p}(A)\right)\). This paper shows that \(A\) also has an advice function in \(\operatorname{PF}\left(\operatorname{NP}(A) \oplus \Sigma_{3}^{p}\right)\). From this new bound, it

The Complexity of McNaughton Functions o
The Complexity of McNaughton Functions of One Variable
✍ Stefano Aguzzoli πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 236 KB

McNaughton functions play the same role in Łukasiewicz logics as Boolean functions do in classical logic. Formulas in one variable are an important ingredient of automated deduction in many-valued logics: the aim of this paper is to establish some results on the complexity of the problems of functio