Prev: logic
Next: "Book Smart" NP-Complete Method: Musatov is closing in... Gaining... People are starting to talk...
From: Graham Cooper on 23 May 2010 19:06
There is/was no polynomial time algorithm to determine if a number is
prime.

However Rabin found a probabilistic solution based on witnesses to
compositeness. Over half of numbers from 1 to any composite number
are witnesses so they are easy to find. If you run 100 iterations of
the algorithm and no witness is found, the number is prime with
probability 1 - (1/2)^100.

P(x is prime) = 99.9999999999999999999999999999999999%.

Such an attack could be used for a halting algorithm, add a parameter
to the probabilistic Halt function which has 3 outcomes.

pHalt(program, input, p) = {Halts | NotHalts | DontKnow}

If half of values of p produce the correct result Halt or NotHalts,
then performing numerous iterations would give an effective procedure
to determine if a program halts or not.

Herc

From: Ludovicus on 23 May 2010 20:39
On May 23, 7:06 pm, Graham Cooper <grahamcoop...(a)gmail.com> wrote:
> There is/was no polynomial time algorithm to determine if a number is
> prime.
> Herc

False. Agrawal et al. discovered an algorithm that determine primality
in polynomial time. Search the article: "Primes in P"
From: Me Me on 23 May 2010 21:05
On May 24, 10:39 am, Ludovicus <luir...(a)yahoo.com> wrote:
> On May 23, 7:06 pm, Graham Cooper <grahamcoop...(a)gmail.com> wrote:
>
> > There is/was no polynomial time algorithm to determine if a number is
> > prime.
> > Herc
>
> False. Agrawal et al. discovered an algorithm that determine primality
> in polynomial time. Search the article: "Primes in P"

Hence is/was

Herc
From: Charlie-Boo on 29 May 2010 22:47
On May 23, 7:06 pm, Graham Cooper <grahamcoop...(a)gmail.com> wrote:
> There is/was no polynomial time algorithm to determine if a number is
> prime.
>
> However Rabin found a probabilistic solution based on witnesses to
> compositeness.  Over half of numbers from 1 to any composite number
> are witnesses so they are easy to find.  If you run 100 iterations of
> the algorithm and no witness is found, the number is prime with
> probability 1 - (1/2)^100.

How do you know they are independent results? Take the chance that it
is prime in that size number. Then each is just an implication of the
fact that the chance is whatever it is. There is no multiplication of
the probabilities.

C-B


>
> P(x is prime) = 99.9999999999999999999999999999999999%.
>
> Such an attack could be used for a halting algorithm, add a parameter
> to the probabilistic Halt function which has 3 outcomes.
>
> pHalt(program, input, p) = {Halts | NotHalts | DontKnow}
>
> If half of values of p produce the correct result Halt or NotHalts,
> then performing numerous iterations would give an effective procedure
> to determine if a program halts or not.
>
> Herc

 | 
Pages: 1
Prev: logic
Next: "Book Smart" NP-Complete Method: Musatov is closing in... Gaining... People are starting to talk...