کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420199 | 683905 | 2011 | 17 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the complexity of enumerating pseudo-intents
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On the complexity of enumerating pseudo-intents On the complexity of enumerating pseudo-intents](/preview/png/420199.png)
چکیده انگلیسی
We investigate whether the pseudo-intents of a given formal context can efficiently be enumerated. We show that they cannot be enumerated in a specified lexicographic order with polynomial delay unless P=NPP=NP. Furthermore we show that if the restriction on the order of enumeration is removed, then the problem becomes at least as hard as enumerating minimal transversals of a given hypergraph. We introduce the notion of minimal pseudo-intents and show that recognizing minimal pseudo-intents is polynomial. Despite their less complicated nature, surprisingly it turns out that minimal pseudo-intents cannot be enumerated in output-polynomial time unless P=NPP=NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 6, 28 March 2011, Pages 450–466
Journal: Discrete Applied Mathematics - Volume 159, Issue 6, 28 March 2011, Pages 450–466
نویسندگان
Felix Distel, Barış Sertkaya,