paragraph_text: Jedno od centralnih pitanja teorije složenosti jest dodaje li slučajnost moć, tj. postoji li problem koji probabilistički Turingov stroj može riješiti u polinomnom vremenu, ali ne i deterministički Turingov stroj? Ili može li deterministički Turingov stroj učinkovito simulirati sve probabilističke Turingove strojeve s najviše polinomnim usporenjem? Trenutno istraživači vjeruju u istinitost potonje tvrdnje, što pak implicira P = BPP. Za isto vrijeme za logaritamski prostor umjesto polinomno vrijeme (je li L = BPLP?) se još više vjeruje da je istinito. U drugu ruku, moć koju slučajnost daje interaktivnim sustavima dokazivanja i jednostavnim algoritmima koje stvara za teške probleme kao što su ispitivanje primalnosti (prostosti) broja u polinomnom vremenu te ispitivanje povezanosti grafa u logaritamskom prostoru, naznačuje da bi slučajnost ipak mogla dodati moć.