كتب relationships with other departments
اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.
علاقات مع الاقسام الاخرى (معلومة)
EXP يحوي كثير من الاقسام المعروفة وذلك للقدرة الهائلة الممنوحة له كما في التعريف حيث أنَّه يحوي القسمين NP و- PSPACE ولكن غير معروف إذا ما الاتجاه الاخر صحيح. اما عن علاقته مع القسم P فهي قد حسمت بواسطة نظرية الوقت الهرمية التي منها ينبع أنَّ . كما أنه بديهيا يتحقق التالي :
- P NP بيسبايس EXPTIME NEXPTIME EXPSPACE
من نظريات الوقت والمساحة الهرمية يتحقق التالي :
لذا فان أحد الاحتواءات الثلاث الاولى يجب أن تكون احتواء فعلي وكذا للثلاث الاخيرات. كما أنَّ رأي معظم علماء الحاسوب يميل إلى أنَّ كل هذه الاحتواءات فعلية.
أحد أهم النظريات هي ربط المسألة EXP=NEXP بالمسألة الشهيرة NP=P , حيث أنه إذا NP=P حينها EXP=NEXP لاحظ ان العكس ليس بالضرورة صحيح إذ انه يمكن أن يكون NP≠P ولكن NEXP=EXP إذ انه يوجد اوراكل حيث أنه NP≠P ولكن NEXP=EXP , وبالضرورة يتحقق EXP≠NEXP إذا وفقط إذا يوجد لغة احادية (أو مسألة احادية) التي هي في NP ولكن ليست في P. وغير معروف إذا ما يوجد لغة كهذه في NP ولكن ليست في P ( ولربما أيضا من الصعب إيجاد واحدة كهذه) .
