الوقت

في نظرية التعقيد الحسابي ، فإن فئة التعقيد NTIME( f ( n )) هي مجموعة مشاكل القرار التي يمكن حلها بواسطة آلة تورينج غير حتمية تعمل في الوقت O ( f ( n ))، حيث O هو ترميز O الكبير ، و f هي دالة ما، و n هو حجم المدخلات (التي سيتم اتخاذ القرار بشأنها).

هذا يعني وجود آلة غير حتمية، بالنسبة لمدخل معين بحجم n ، ستعمل، لجميع مسارات الحساب، في زمن قدره O ( f ( n )) (أي ضمن مضاعف ثابت لـ f ( n )، عندما يكون n أكبر من قيمة معينة)، وسترفض دائمًا المدخل إذا كانت إجابة مسألة القرار "لا" لهذا المدخل، بينما إذا كانت الإجابة "نعم"، فستقبل الآلة هذا المدخل لمسار حساب واحد على الأقل. وبالمثل، توجد آلة تورينغ حتمية M تعمل في زمن قدره O ( f ( n )) وقادرة على التحقق من شهادة بطول O ( f ( n )) لمدخل ما؛ إذا كان المدخل "نعم"، فسيتم قبول شهادة واحدة على الأقل، وإذا كان المدخل "لا"، فلن تتمكن الآلة من قبول أي شهادة.

المساحة المتاحة للآلة غير محدودة، على الرغم من أنها لا يمكن أن تتجاوز O ( f ( n ))، لأن الوقت المتاح يحد من مقدار الشريط الذي يمكن الوصول إليه.

يمكن تعريف فئة التعقيد المعروفة NP بدلالة NTIME على النحو التالي:

${\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})}$

وبالمثل، يتم تعريف الفئة NEXP بدلالة NTIME:

${\displaystyle {\mathsf {NEXP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}$

تنص نظرية التسلسل الهرمي الزمني غير الحتمي على أن الآلات غير الحتمية يمكنها حل المزيد من المشاكل في وقت أطول بشكل مقارب.

يرتبط NTIME أيضًا بـ DSPACE بالطريقة التالية. لأي دالة قابلة للإنشاء زمنيًا t ( n )، لدينا

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$.

يُعدّ ATIME تعميمًا لـ NTIME ، وهو مُعرّف باستخدام آلات تورينج المتناوبة . وقد تبيّن أن

${\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {ATIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))}$.

حديقة التعقيد : NTIME( f ( n )) .