Алайда, тәжірибеде, қарапайым сандардың тізімін алудың орнына, көбінесе берілген санның қарапайым екенін тексеру қажет. Бұл мәселені шешу алгоритмі қарапайымдық тестілері деп аталады. Қарапайымдылық полиномиалдық тестерінің көпшілігі бар, бірақ олардың көпшілігі ықтималдық (мысалы, Миллер  Рабин тесті) және криптографияның қажеттіліктері үшін қолданылады. 2002 жылы қарапайымдықты тексеру мәселесі жалпы полиномиалды түрде шешілетіндігі дәлелденді, бірақ ұсынылған детерминирленген тест Агравала  Каяла  Саксена өте үлкен есептеу күрделілігіне ие, бұл оны практикалық қолдануды қиындатады.
Қандай тесттің есептеу күрделілігі өте жоғары?
Агравала  Каяла  Саксена