TC (күрделілігі) - TC (complexity)

Жылы теориялық информатика және арнайы есептеу күрделілігі теориясы және тізбектің күрделілігі, ТК Бұл күрделілік сыныбы туралы шешім қабылдау проблемалары олар шекті тізбектер арқылы танылуы мүмкін Буль тізбектері бірге ЖӘНЕ, НЕМЕСЕ, және Көпшіліктің қақпалары. Әрқайсысы үшін мен, күрделілік класы ТКмен тереңдіктің шекті тізбегі бойынша танылатын барлық тілдерден тұрады , көпмүшелік өлшемі және шектеусіз желдеткіш. Сынып ТК арқылы анықталады

NC және айнымалы токқа қатысты

ТК арасындағы байланыс, NC және Айнымалы иерархияны келесідей қорытындылауға болады:

Атап айтқанда, біз мұны білеміз

Бірінші қатаң оқшаулау осыдан туындайды NC0 барлық кіріс биттеріне тәуелді кез-келген функцияны есептей алмайды. Осылайша маңызды емес мәселені таңдау Айнымалы0 және барлық биттерге байланысты екі классты бөледі. (Мысалы, НЕМЕСЕ функциясын қарастырыңыз.) Қатаң оқшаулау Айнымалы0ТК0 паритет және көпшілік (екеуі де бар) ТК0) жоқ екендігі көрсетілді Айнымалы0.[1][2]

Жоғарыда келтірілген шектеулердің бірден-бір салдары ретінде бізде NC = AC = TC болады.

Әдебиеттер тізімі

  1. ^ Фурст, Меррик; Сакс, Джеймс Б.; Сипсер, Майкл (1984), «Паритет, тізбектер және полиномдық уақыт иерархиясы», Математикалық жүйелер теориясы, 17 (1): 13–27, дои:10.1007 / BF01744431, МЫРЗА  0738749.
  2. ^ Хестад, Йохан (1989), «Шағын тереңдік тізбектері үшін оңтайлы төменгі шекаралар», Микали, Сильвио (ред.), Кездейсоқтық және есептеу (PDF), Компьютерлік зерттеулердегі жетістіктер, 5, JAI Press, 6–20 бет, ISBN  0-89232-896-7, мұрағатталған түпнұсқа (PDF) 2012-02-22
  • Вольмер, Хериберт (1999). Схеманың күрделілігіне кіріспе. Берлин: Шпрингер. ISBN  3-540-64310-9.