Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Primtalstestning er af klassen P

0 views
Skip to first unread message

Jeppe Stig Nielsen

unread,
Aug 16, 2002, 9:28:35 AM8/16/02
to
Har I hřrt (jeg ser det fřrst nu) at nogle indere har bevíst at
problemet at afgřre hvorvidt et forelagt tal er et primtal eller
ej, kan lřses i polynomiel tid?

Se http://mathworld.wolfram.com/news/2002-08-07_primetest/


--
Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «

"Je n'ai pas eu besoin de cette hypothčse (I had no need of that
hypothesis)" --- Laplace (1749-1827)

Jens Axel Søgaard

unread,
Aug 16, 2002, 9:45:12 AM8/16/02
to
Jeppe Stig Nielsen wrote:
> Har I hørt (jeg ser det først nu) at nogle indere har
> bevíst at problemet at afgøre hvorvidt et forelagt tal er
> et primtal eller ej, kan løses i polynomiel tid?
>
> Se http://mathworld.wolfram.com/news/2002-08-07_primetest/

Det blev nævnt på Slashdot for en uges tid siden:

http://slashdot.org/article.pl?sid=02/08/07/0151216&mode=nested&tid=172

Men artiklen selv var mere interessant end diskussionen.

--
Jens Axel Søgaard

Kim Hansen

unread,
Aug 16, 2002, 10:52:36 AM8/16/02
to
Jeppe Stig Nielsen <ma...@jeppesn.dk> writes:

> Har I hørt (jeg ser det først nu) at nogle indere har bevíst at
> problemet at afgøre hvorvidt et forelagt tal er et primtal eller
> ej, kan løses i polynomiel tid?
>
> Se http://mathworld.wolfram.com/news/2002-08-07_primetest/

Er det ikke åbenlyst at det kan løses i polynomiel tid. F.eks. kunne
man undersøge tallet N i O(N^2) tid ved at gange alle tal 2, ..., N
med alle tal 2, ..., N sammen og se om et af resultaterne er N.

Efter at have læst lidt på det er jeg kommet frem til at de nok mener
'polynomisk i tallets længde', hvilket også passer med deres
kompleksitet på O(log^12 N).

--
Kim Hansen | |\ _,,,---,,_ | Det er ikke
Dalslandsgade 8, A708 | /,`.-'`' -. ;-;;,_ | Jeopardy.
2300 København S | |,4- ) )-,_. ,\ ( `'-' | Svar _efter_
Phone: 32 88 60 86 | '---''(_/--' `-'\_) | spørgsmålet.

Jens Axel Søgaard

unread,
Aug 16, 2002, 12:11:51 PM8/16/02
to
Kim Hansen wrote:
> Jeppe Stig Nielsen <ma...@jeppesn.dk> writes:

> Er det ikke åbenlyst at det kan løses i polynomiel tid.
> F.eks. kunne man undersøge tallet N i O(N^2) tid ved at
> gange alle tal 2, ..., N med alle tal 2, ..., N sammen og
> se om et af resultaterne er N.
>
> Efter at have læst lidt på det er jeg kommet frem til at
> de nok mener 'polynomisk i tallets længde', hvilket også
> passer med deres kompleksitet på O(log^12 N).

Inputstørrelsen sættes ganske rigtigt til antallet af bit
i tallets binære repræsentation.

--
Jens Axel Søgaard

Peter Makholm

unread,
Aug 16, 2002, 1:37:35 PM8/16/02
to
"Jens Axel Søgaard" <use...@soegaard.net> writes:

> Det blev nævnt på Slashdot for en uges tid siden:

[...]

> Men artiklen selv var mere interessant end diskussionen.

Øhhhh, ja. Sådan er Slashdot og ligende websteder.

--
Peter Makholm | Perhaps that late-night surfing is not such a
pe...@makholm.net | waste of time after all: it is just the web
http://hacking.dk | dreaming
| -- Tim Berners-Lee

smųlf

unread,
Aug 16, 2002, 4:11:59 PM8/16/02
to
WOW......kanon!

Hva skal vi bruge det til?


"Jeppe Stig Nielsen" <ma...@jeppesn.dk> wrote in message
news:3D5CFE03...@jeppesn.dk...
> Har I hørt (jeg ser det først nu) at nogle indere har bevíst at
> problemet at afgøre hvorvidt et forelagt tal er et primtal eller
> ej, kan løses i polynomiel tid?


>
> Se http://mathworld.wolfram.com/news/2002-08-07_primetest/
>
>
> --
> Jeppe Stig Nielsen <URL:http://jeppesn.dk/>. «
>

> "Je n'ai pas eu besoin de cette hypothèse (I had no need of that
> hypothesis)" --- Laplace (1749-1827)


Bertel Lund Hansen

unread,
Aug 16, 2002, 4:45:27 PM8/16/02
to
smølf skrev:

>Hva skal vi bruge det til?

Hvad skal vi bruge dit bevis til?

--
Bertel
http://bertel.lundhansen.dk/ FIDUSO: http://fiduso.dk/

Jens Axel Søgaard

unread,
Aug 17, 2002, 4:14:46 AM8/17/02
to
smølf wrote:
> WOW......kanon!
>
> Hva skal vi bruge det til?

Sove roligere om natten.

--
Jens Axel Søgaard

Michael Knudsen

unread,
Aug 17, 2002, 5:00:03 AM8/17/02
to
On Fri, 16 Aug 2002 22:45:27 +0200, Bertel Lund Hansen wrote:

> Hvad skal vi bruge dit bevis til?

Hvilket bevis?

/Michael Knudsen

Bertel Lund Hansen

unread,
Aug 17, 2002, 5:09:33 AM8/17/02
to
Michael Knudsen skrev:

>Hvilket bevis?

<news:3d5ba3b0$0$671$ba62...@nntp04.dk.telia.net>

Michael Knudsen

unread,
Aug 17, 2002, 9:04:10 AM8/17/02
to
On Sat, 17 Aug 2002 11:09:33 +0200, Bertel Lund Hansen wrote:

> <news:3d5ba3b0$0$671$ba62...@nntp04.dk.telia.net>

Hmmm...hvor smider man sådan et link hen?!

/Michael Knudsen

Bertel Lund Hansen

unread,
Aug 17, 2002, 10:05:23 AM8/17/02
to
Michael Knudsen skrev:

>Hmmm...hvor smider man sådan et link hen?!

Prøv at dobbelklikke på det.

I mit program kan jeg højreklikke og vælge "Lauch URL".

Ivar

unread,
Aug 17, 2002, 10:11:26 AM8/17/02
to

Michael Knudsen skrev:

> > <news:3d5ba3b0$0$671$ba62...@nntp04.dk.telia.net>
>
> Hmmm...hvor smider man sådan et link hen?!

Hvad man skal gøre i din news-reader ved jeg ikke, men fx OE
og Netscape genkender linket og man skal blot trykke på det.
Linket referer til starten af en tråd sendt her i gruppen 15/8
kl. 14.54.

Smølf har send masser af tåbelige indlæg i denne og andre
grupper. Han er en troll og derfor bør han stoppes.


Ivar


0 new messages