5 lines
315 B
Markdown
5 lines
315 B
Markdown
# Probabilistic Polynomial Time
|
|
|
|
- for a given problem, a PPT algorithm for the problem runs in P-time, with a high (likely non-one) probability of giving the correct answer
|
|
- takes randomness as an input
|
|
- impossible to guarantee the real solution without running the algorithm on all possible randomness (NP)
|