Displaying similar documents to “Un'estensione del teorema di Löb”

Questo numero è primo? Sì, forse, dipende ...

Luisella Caire, Umberto Cerruti (2006)

Bollettino dell'Unione Matematica Italiana

Similarity:

In this paper we outline some algorithms answering the question if a given number is prime: primally criteria, that are deterministic (they positively reply yes or not) and unconditional, but inefficient (technically not polynomial-time); algoritms that are efficient, but only probabilistic (to say they give absolute certainty if they answer not, whereas they only give a low boundary of the probability for the number to be prime if they answer yes); algorithms that are the same time...