RP (złożoność)
W teorii złożoności obliczeniowej losowy czas wielomianowy ( RP ) to klasa złożoności problemów, dla których istnieje probabilistyczna maszyna Turinga o następujących właściwościach:
| Algorytm RP (1 przebieg) | ||
|---|---|---|
|
Uzyskano odpowiedź
Prawidłowa odpowiedź |
Tak | NIE |
| Tak | ≥ 1/2 | ≤ 1/2 |
| NIE | 0 | 1 |
| Algorytm RP ( n przebiegów) | ||
|
Uzyskano odpowiedź
Prawidłowa odpowiedź |
Tak | NIE |
| Tak | ≥ 1 - 2 - n | ≤ 2 - rz |
| NIE | 0 | 1 |
| algorytm co-RP (1 przebieg) | ||
|
Uzyskano odpowiedź
Prawidłowa odpowiedź |
Tak | NIE |
| Tak | 1 | 0 |
| NIE | ≤ 1/2 | ≥ 1/2 |
- Zawsze działa w czasie wielomianowym w rozmiarze wejściowym
- Jeśli poprawna odpowiedź brzmi NIE, zawsze zwraca NIE
- Jeśli poprawna odpowiedź brzmi TAK, to zwraca TAK z prawdopodobieństwem co najmniej 1/2 (w przeciwnym razie zwraca NIE).
Innymi słowy, algorytm może rzucić naprawdę losową monetą podczas działania. Jedynym przypadkiem, w którym algorytm może zwrócić TAK, jest sytuacja, w której rzeczywista odpowiedź brzmi TAK; dlatego jeśli algorytm kończy działanie i daje TAK, to poprawna odpowiedź brzmi zdecydowanie TAK; jednak algorytm może zakończyć się NIE, niezależnie od rzeczywistej odpowiedzi. Oznacza to, że jeśli algorytm zwraca NIE, może być błędny.
Niektórzy autorzy nazywają tę klasę R , chociaż ta nazwa jest częściej używana dla klasy języków rekurencyjnych .
Jeśli poprawna odpowiedź brzmi TAK, a algorytm zostanie uruchomiony n razy, a wynik każdego uruchomienia jest statystycznie niezależny od pozostałych, to co najmniej raz zwróci TAK z prawdopodobieństwem co najmniej 1 − 2 − n . Jeśli więc algorytm zostanie uruchomiony 100 razy, to prawdopodobieństwo, że za każdym razem poda błędną odpowiedź, jest mniejsze niż prawdopodobieństwo, że promienie kosmiczne uszkodziły pamięć komputera obsługującego algorytm. W tym sensie, jeśli dostępne jest źródło liczb losowych, większość algorytmów w RP jest wysoce praktyczna.
Ułamek 1/2 w definicji jest dowolny. Zbiór RP będzie zawierał dokładnie te same problemy, nawet jeśli 1/2 zostanie zastąpione dowolnym stałym niezerowym prawdopodobieństwem mniejszym niż 1; tutaj stała oznacza niezależną od danych wejściowych do algorytmu.
Definicja formalna
Język L jest w RP wtedy i tylko wtedy, gdy istnieje probabilistyczna maszyna Turinga M taka, że
- M działa dla czasu wielomianowego na wszystkich wejściach
- Dla wszystkich x w L , M wyprowadza 1 z prawdopodobieństwem większym lub równym 1/2
- Dla wszystkich x nie w L , M wyprowadza 0
Alternatywnie, RP można zdefiniować za pomocą tylko deterministycznych maszyn Turinga. Język L jest w RP wtedy i tylko wtedy, gdy istnieje wielomian p i deterministyczna maszyna Turinga M taka, że
- M działa dla czasu wielomianowego na wszystkich wejściach
- Dla wszystkich x w L , ułamek łańcuchów y o długości p (| x |), które spełniają jest większy lub równy 1/2
- Dla wszystkich x nie w L i wszystkich łańcuchów y o długości p (| x |),
W tej definicji ciąg y odpowiada wynikowi losowych rzutów monetą, które wykonałaby probabilistyczna maszyna Turinga. W przypadku niektórych zastosowań ta definicja jest preferowana, ponieważ nie wspomina o probabilistycznych maszynach Turinga.
Powiązane klasy złożoności
Definicja RP mówi, że odpowiedź TAK jest zawsze poprawna, a odpowiedź NIE może być błędna, ponieważ instancja TAK może zwrócić odpowiedź NIE. Ko-RP klasy złożoności jest uzupełnieniem, gdzie odpowiedź TAK może być błędna, podczas gdy odpowiedź NIE jest zawsze poprawna.
Klasa BPP opisuje algorytmy, które mogą dawać błędne odpowiedzi zarówno w przypadkach TAK, jak i NIE, a zatem zawiera zarówno RP , jak i co-RP . Przecięcie zbiorów RP i co-RP nazywa się ZPP . Tak jak RP można nazwać R , niektórzy autorzy używają nazwy co-R zamiast co-RP .
Podłączenie do P i NP
P jest podzbiorem RP , który jest podzbiorem NP . Podobnie P jest podzbiorem co-RP , który jest podzbiorem co-NP . Nie wiadomo, czy inkluzje te są ścisłe. Jeśli jednak powszechnie uważana hipoteza P = BPP jest prawdziwa, to RP , co-RP i P załamują się (wszystkie są równe). Zakładając dodatkowo, że P ≠ NP , oznacza to, że RP jest ściśle zawarte w NP . Nie wiadomo, czy RP = co-RP , czy też RP jest podzbiorem przecięcia NP i co-NP , chociaż sugerowałoby to P = BPP .
Naturalnym przykładem problemu w ko-RP, o którym obecnie nie wiadomo, że występuje w P , jest testowanie tożsamości wielomianów , problem z podjęciem decyzji, czy dane wielowymiarowe wyrażenie arytmetyczne na liczbach całkowitych jest wielomianem zerowym. Na przykład x · x - y · y - ( x + y )·( x - y ) jest wielomianem zerowym, podczas gdy x · x + y · y nie jest.
Alternatywną charakterystyką RP , która jest czasami łatwiejsza w użyciu, jest zestaw problemów rozpoznawanych przez niedeterministyczne maszyny Turinga , w których maszyna akceptuje wtedy i tylko wtedy, gdy akceptuje przynajmniej pewien stały ułamek ścieżek obliczeniowych, niezależny od wielkości wejściowej. Z drugiej strony NP potrzebuje tylko jednej akceptującej ścieżki, która mogłaby stanowić wykładniczo mały ułamek ścieżek. Ta charakterystyka sprawia, że fakt, że RP jest podzbiorem NP, jest oczywisty.