كثير من المشكلات - الممثله على شكل قراف - تكون صعبة الحل NP بشكلها الطبيعي
لكن عندما نمثلها على شكل clique tree تكون سهلة الحل polynomial complexity .. مالسبب؟
وهل هناك خصائص معينة مشتركة للمشاكل هذه؟
اعتقد ان السبب هو اننا نفترض ان المشكلة لها bound في قيمة الtreewidth .
عادة تسمى bounded tree width .. الخوارزميات عادة تكون exponent لهذه القيمة وبما انها constant في المشكلة تصبح polynomial
علوم الحاسب: كل ما يتعلق بالاساس العلمي للحاسب من دراسة للخوارزميات و هيكلة البيانات
التعليقات