سایپرز، باشگاه دانش - ارائه دهنده مقالات ژورنالهای خارجی

اطلاعات و مشخصات مقاله

[ 90 | جستجو | فهرست کلمات کلیدی | فهرست موضوعات | فهرست نویسندگان | فهرست ناشران | فهرست ژورنالها ]


عنوان مقاله:یک کلیت از پیچیدگی گسترش است که قطاری P
ناشر: [ Elsevier BV ]
ژورنال
دوره (شماره):115 (6-8)
سال انتشار:June–August 2015
شماره صفحات: 588593588-593
نشانگر دیجیتالی شیء:[ 10.1016/j.ipl.2015.02.005 ]
شما اینجا هستید:
  1. Scipers, the Knowledge ClubScipers »
  2. Elsevier BV »
  3. Information Processing Letters »
  4. A generalization of extension complexity that captures P

دسترسی بین المللی

اگر شما در داخل کشور (ایران) هستید و این صفحه را مشاهده می کنید، نشان می دهد که IP شما به هر دلیلی در لیست IP های ایران ثبت نشده است. برای رفع این مشکل کافی است IP خود را که در پایین این پیام درج شده از طریق آدرس ایمیل support@scipers.com به ما اطلاع دهید. پس از دریافت درخواست، کارشناسان فنی موضوع را بررسی می نمایند و در صورتی که محل اتصال شما از کشور ایران بوده باشد، به لیست استفاده کنندگان مجاز افزوده می شوید.
IP: 54.235.55.253

اطلاعات استنادی

اطلاعات استنادی این مقاله را به نرم افزارهای مدیریت اطلاعات علمی و استنادی ارسال نمایید و در تحقیقات خود از آن استفاده نمایید.

 

به اشتراک گذاری

این صفحه را با استفاده از انواع شبکه های اجتماعی با دوستان خود به اشتراک بگذارید.

خلاصه مقاله، نویسندگان و کلمات کلیدی

A Generalization Of Extension Complexity That Captures P


مقاله: یک کلیت از پیچیدگی گسترش است که قطاری P

نويسند‌گان:


خلاصه مقاله:


In this paper we propose a generalization of the extension complexity of a polyhedron Q. On the one hand it is general enough so that all problems in P can be formulated as linear programs with polynomial size extension complexity. On the other hand it still allows non-polynomial lower bounds to be proved for NP-hard problems independently of whether or not P=NP. The generalization, called H-free extension complexity, allows for a set of valid inequalities H to be excluded in computing the extension complexity of Q. We give results on the H-free extension complexity of hard matching problems (when H are the odd-set inequalities) and the traveling salesman problem (when H are the subtour elimination constraints).


 


كلمات كليدي:

Computational complexity , Extended formulations , Extension complexity , Linear programming, Lower bounds , Polytopes , Theory of computation , Combinatorial problems, Computational complexity, Extended formulations, Extension complexity, Linear programming, Lower bounds, Polytopes, Theory of computation
Computational complexity , فرمولاسیون تمدید , پیچیدگی فرمت , برنامه ریزی خطی , کران پایین , Polytopes , Theory of computation , ترکیبی مشکلات, پیچیدگی محاسباتی, فرمولاسیون تمدید, پیچیدگی فرمت, برنامه ریزی خطی, مرزهای پایین, Polytopes, نظریه محاسبات


موضوعات:

Computer Science Applications, Information Systems, Signal Processing, Theoretical Computer Science



[ ]

فهرست مقالات مرتبط و مشابه

  1. , (2010) 'New Imaging Captures the Brainʼs Complexity', Neurology Now, Ovid Technologies (Wolters Kluwer Health), pp:9-10
  2. Smart, Ashley G. (2011) 'Minimalist model captures water-cycle complexities', Physics Today, AIP Publishing, pp:19-21
  3. Gallinari, Patrick, Cibas, Tautvydas (1998) 'Complexity Control and Generalization in Multilayer Perceptrons', Advances in Computational Management Science, Springer Nature, pp:13-25
  4. , (2012) 'An extension of data automata that captures XPath', Logical Methods in Computer Science, Logical Methods in Computer Science, pp:0-0
  5. Michaels, Gerald (2014) 'Making it real: Psychological assessment that captures a client's complexity and uniqueness.', PsycCRITIQUES, American Psychological Association (APA), pp:0-0
  6. Avis, David , Tiwary, Hans Raj (2014) 'On the extension complexity of combinatorial polytopes', Mathematical Programming, Springer Science + Business Media, pp:0-0
  7. Bojanczyk, Mikolaj, Lasota, Slawomir (2010) 'An Extension of Data Automata that Captures XPath', 2010 25th Annual IEEE Symposium on Logic in Computer Science, Institute of Electrical and Electronics Engineers (IEEE), pp:0-0
  8. Karhumaki, Juhani, Saarela, Aleksi, Zamboni, Luca Q. (2013) 'On a generalization of Abelian equivalence and complexity of infinite words', Journal of Combinatorial Theory, Series A, Elsevier BV, pp:2189-2206
  9. Janzing, D. (2006) 'Implementation complexity of physical processes as a natural extension of computational complexity', Fortschritte der Physik, Wiley-Blackwell, pp:882-897
  10. Byrnes, Christopher I., Georgiou, Tryphon T., Lindquist, Anders, Megretski, Alexander (2004) 'Generalized interpolation in $H^infty$ with a complexity constraint', Trans. Amer. Math. Soc., American Mathematical Society (AMS), pp:965-987

 

فهرست مراجع و منابع




 

برگشت به بالا
رونمایی از اولین و تنها ربات تلگرامی جستجوی مقالات ژورنالی
×