Snížení prvního řádu - First-order reduction

v počítačová věda, a snížení prvního řádu je velmi slabý typ snížení mezi dvěma výpočetní problémy v teorie výpočetní složitosti. Redukce prvního řádu je redukce, při které je každá součást omezena na to, aby byla ve třídě FO problémů vypočítatelných v logika prvního řádu.

Protože máme , redukce prvního řádu jsou slabší redukce než redukce logspace.

Mnoho důležitých tříd složitosti je uzavřeno v rámci redukcí prvního řádu a mnoho tradičních kompletní problémy jsou také prvního řádu úplné (Immerman 1999, s. 49-50). Například, Konektivita ST je FO-kompletní pro NL, a NL je uzavřen pod redukcemi FO (Immerman 1999, s. 51) (jak jsou P, NP a většina ostatních „vychovaných“ tříd).

Reference

  • Immerman, Neil (1999). Popisná složitost. New York: Springer-Verlag. ISBN  0-387-98600-6.