Teoria informatykiobiekt

RP

randomized polynomial

Klasa problemów rozstrzygalnych w wielomianowym czasie przez maszynę probabilistyczną z jednostronnym błędem: nigdy nie myli się dla instancji negatywnych.

Typ: obiekt
Pojęcie nadrzędne: probabilistyczna klasa złożoności
Kategoria: Teoria informatyki · Teoria zlozonosci klasy
Źródło: Arora & Barak, Computational Complexity, rozdz. 7

Zobacz też

BPPZPP

Powiązane pojęcia · Matematyka dyskretna i teoria obliczeń

liczba kardynalna

Miara mocy zbioru wyrażająca jego liczność, uogólniająca pojęcie liczby elementów na zbiory nieskończone.

zbiór przeliczalny

Zbiór równoliczny z pewnym podzbiorem liczb naturalnych, tj. skończony lub równoliczny ze zbiorem liczb naturalnych.

kwantyfikator

Operator wiążący zmienną w formule, wyrażający zakres jej obowiązywania: ogólny (dla każdego) lub egzystencjalny (istnieje).

logika pierwszego rzędu

System logiczny dopuszczający kwantyfikację po elementach dziedziny, z predykatami, funkcjami i relacjami, ale bez kwantyfikacji po zbiorach.

predykat

Wyrażenie oznaczające relację lub własność elementów dziedziny, dające zdanie po podstawieniu argumentów.

twierdzenie o zupełności

Wynik stwierdzający, że każda formuła prawdziwa we wszystkich modelach teorii jest w niej dowodliwa.

Chcesz wykorzystać AI w swojej firmie?

Wdrażamy chatboty, agentów głosowych i automatyzacje dla MŚP. Pierwsza konsultacja jest bezpłatna.

Bezpłatna konsultacja

← Wróć do słownika