Бірінші ретті төмендету - First-order reduction

Жылы Информатика, а бірінші ретті төмендету өте әлсіз түрі болып табылады төмендету екеуінің арасында есептеулер жылы есептеу күрделілігі теориясы. Бірінші ретті қысқарту - бұл әрбір компоненттің сыныпта болуына шектеу қою FO есептелетін есептер бірінші ретті логика.

Бізде болғандықтан ${displaystyle {mbox {FO}} subsetneq {mbox {L}}}$, бірінші ретті қысқартулар төмендеулерге қарағанда әлсіз редукциялар болып табылады кеңістікті азайту.

Күрделіліктің көптеген маңызды сыныптары бірінші ретті қысқартулар бойынша жабылады, ал дәстүрлі түрде толық мәселелер бірінші ретті де аяқталған (Иммерман 1999 ж. 49-50). Мысалға, ST-байланыс үшін FO аяқталды NL, және NL FO төмендеуі кезінде жабық (Immerman 1999, 51-бет) (қалай болса солай) P, NP, және көптеген басқа «жақсы тәртіпті» сыныптар).

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

• Иммерман, Нил (1999). Сипаттамалық күрделілік. Нью-Йорк: Спрингер-Верлаг. ISBN  0-387-98600-6.

P ≟ NP

Бұл теориялық информатика - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.

Бұл математикалық логика - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.