---

Jeg er i gang med at løse nogle forskellige "talgåder" og jeg er kørt fast i
denne opgave:

Find to tal i tallet herunder, der giver resultatet 8647492 når det ganges
med hinanden
65887214

Jeg har en facitliste, så jeg kender svaret men er interesseret i metoden
man skal bruge for at løse opgaven hurtigst muligt.

- Ole Kristensen

---

"Ole Kristensen" <ok@amu-randers.dk> skrev i en meddelelse
news:U1%r8.15429$iY5.662610@news010.worldonline.dk...
> Jeg er i gang med at løse nogle forskellige "talgåder" og jeg er kørt fast
i
> denne opgave:
>
> Find to tal i tallet herunder, der giver resultatet 8647492 når det ganges
> med hinanden
> 65887214

Hvad mener du med at finde 2 tal?
1. Må man selv vælge fra 0 - 65887214 ?
2. Skal de 2 tal bestå af tal i der fremkommer direkte i ovennævnte tal? fx
6588721 eller 887214
3. Skal de 2 tal bestå en vilkårlig opstilling af talet: 65887214?

---

> Hvad mener du med at finde 2 tal?
> 1. Må man selv vælge fra 0 - 65887214 ?
> 2. Skal de 2 tal bestå af tal i der fremkommer direkte i ovennævnte tal?
fx
> 6588721 eller 887214
> 3. Skal de 2 tal bestå en vilkårlig opstilling af talet: 65887214?

Brian,

Tak for din interesse for løsningen!

Man skal finde 2 tal som ganget med hinanden giver 8647492

De to tal skal indeholde cifrene: 6 5 8 8 7 2 1 4
Alle cifre SKAL anvendes, men hvert ciffer må kun anvendes én gang!

Facit er: 1258 x 6874 = 8647492
Altså er alle 8 cifre fra: 6 5 8 8 7 2 1 4 anvendt!

Men jeg vil gerne finde en metode, så jeg kan finde svar på tilsvarende
opgaver i fremtiden.

Med venlig hilsen

Ole Kristensen

---

Ole Kristensen wrote:
>
> De to tal skal indeholde cifrene: 6 5 8 8 7 2 1 4
> Alle cifre SKAL anvendes, men hvert ciffer må kun anvendes én gang!
>
> Facit er: 1258 x 6874 = 8647492
> Altså er alle 8 cifre fra: 6 5 8 8 7 2 1 4 anvendt!
>
> Men jeg vil gerne finde en metode, så jeg kan finde svar på tilsvarende
> opgaver i fremtiden.

Jeg véd ikke om der er smarte måder, men man kan jo starte med at
opløse det ønskede produkt i primfaktorer (fx hvis man har et program
der gør det automatisk). Det giver her 8647492=2·2·7·17·37·491.
Men der er jo stadig en del måder at inddele disse faktorer i to
klasser på ...

--
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)

---

Tak for besvarelserne!

Primtalsmetoden ser ud til at være rimelig effektiv.
Jeg har linet mulighederne op i et regneark og farvekodet dem dernedad
(udeladt de mest usandsynlige) og udregnede de 2 resultater.

Og fandt så at primtallene:
491x37x2 = 6874 og
37x17x2 = 1258

Og så er alle cifrene i talrækken 6 5 8 8 7 2 1 4 anvebndt!

Men lige et tillægsspørgsmål: Hvordan finder man primtallene ud af 6 5 8 8 7
2 1 4??? (mystificeret!)

Med venlig hilsen og tak for hjælpen

Ole Kristensen

---

Ole Kristensen wrote:

> Men lige et tillægsspørgsmål: Hvordan finder man primtallene ud af 6 5 8 8
> 7 2 1 4??? (mystificeret!)

Han finder primtallene ud fra resultatet: 8647492 . Ikke ud fra den
vilkårlige sekvens af cifre - 65887214.

-Claus

---

"Claus Rasmussen" <clr@cc-consult.dk> skrev i en meddelelse
news:a8rdp0$s6k$1@sunsite.dk...
> Ole Kristensen wrote:
>
> > Men lige et tillægsspørgsmål: Hvordan finder man primtallene ud af 6 5 8
8
> > 7 2 1 4??? (mystificeret!)
>
> Han finder primtallene ud fra resultatet: 8647492 . Ikke ud fra den
> vilkårlige sekvens af cifre - 65887214.
>
> -Claus

Nå ja, det er rigtigt!

Men hvordan? Er der en formel til den slags?

Ole Kristensen

---

Ole Kristensen wrote:

> Men hvordan? Er der en formel til den slags?

Der er nogle små smarte programmer til den slags Ellers er
en simpel algoritme:

primtalsfaktorisering af N:
For hvert primtal fra 2 til N
Sålænge primtallet dividerer N
udskriv primtal
sæt N = N / primtal
SlutSå
SlutFor

Meget simpelt - og /meget/ dyrt i beregningstid, hvis N er stor
nok.

Det er for i øvrigt dét, der gør vores krypteringsalgoritmer
så sikre som de er. Kunne man primtalsfaktorisere på en hurtigere
måde, ville man nemt kunne bryde koderne i kryptering.

-Claus

---

In <a8rp9p$hlf$1@sunsite.dk> Claus Rasmussen <clr@cc-consult.dk> writes:

>Ole Kristensen wrote:

>> Men hvordan? Er der en formel til den slags?

>Der er nogle små smarte programmer til den slags Ellers er
>en simpel algoritme:

> primtalsfaktorisering af N:
> For hvert primtal fra 2 til N
> Sålænge primtallet dividerer N
> udskriv primtal
> sæt N = N / primtal
> SlutSå
> SlutFor

>Meget simpelt - og /meget/ dyrt i beregningstid, hvis N er stor
>nok.

>Det er for i øvrigt dét, der gør vores krypteringsalgoritmer
>så sikre som de er. Kunne man primtalsfaktorisere på en hurtigere
>måde, ville man nemt kunne bryde koderne i kryptering.

> -Claus

Der er en hel del krøller på det. Fx er det hurtigere at faktorisere
primtal end ovenstående algoritme kunne tyde på.

ikke-primtal af bestemte former kan også være lettere at knække.
Fx er fibonacci-tal (1 1 2 3 5 8 13 21 34 55 89 144 233 377 ..)
der står på en lige position 1 3 8 21 55 144 377 delelige med
det, der står på den "halve" position 1,1,2,3,5,8,13...
Der er dog ikke nok af den slags til at det kan betale sig at
checke noget særligt for det. Men PGP og andre programmer, der har
brug for store tal med specielle egenskaber checker forhåbentligt
den slags.

Jeg tror ikke at det har været sagt, men det er let at finde
ud af hvor mange tal, der går op i N, hvis man har en
primtalsfaktorisering af N. Man kigger på de forskellige
primtal i faktoriseringen og ser hvor mange gange de forekommer.

Fx 60 = 2 * 2 * 3 * 5
2 forekommer 2 gange
3 forekommer 1 gang
5 forekommer 1 gang

Hvis et tal skal gå op i N må det være et produkt af de samme
primtal som N og de må højst forekomme lige så mange gange som
de gør i N. Dvs i eksemplet ovenfor må
2 forekomme 0 1 eller 2 gange
3 forekomme 0 eller 1 gang
5 forekomme 0 eller 1 gang

Dvs
3 muligheder mht 2
2 muligheder mht 3
2 muligheder mht 5
og da man kan vælge frit er der 3*2*2 = 12 tal, der går op i 60

Og de er netop 1,2,3,4,5,6,10,12,15,20,30,60

mvh Birger Nielsen (bnielsen@daimi.au.dk)

---

Kai Birger Nielsen wrote:

> Der er en hel del krøller på det. Fx er det hurtigere at faktorisere
> primtal end ovenstående algoritme kunne tyde på.

Ja. Jeg har også haft algebra

Landrock excellerede i at vise os alle mulige fantastiske tricks til at
finde primtal. Den vildeste var et eksempel, hvor han viste, at alle tal
med mindre end omkring 100 cifre havde en bestemt egenskab, der gjorde
dem en hel del nemmere at faktorisere. Advarsel: SVJH og jeg dumpede

-Claus

---

"Ole Kristensen" <ok@amu-randers.dk> skrev i en meddelelse
news:%7ds8.19871$iY5.700775@news010.worldonline.dk...

> Men hvordan? Er der en formel til den slags?

Desværre nej. Faktisk er det så svært at faktorisere store tal,
at man anvender det til at lave sikre koder i forbindelse med
dankort med mere.

Jeg har fundet et lille Java-program, som kan faktorisere alle
de tal, du har brug for. De har endda en liste med historiske
eksempler.

http://www.cryptographic.co.uk/factorise.html

--
Jens Axel Søgaard

---

"Jens Axel Søgaard" wrote:
>
> Jeg har fundet et lille Java-program, som kan faktorisere alle
> de tal, du har brug for. De har endda en liste med historiske
> eksempler.

Der er jo også tallet F5 = 2^(2^5)+1 = 4.294.967.297 faktoriseret af
Euler i 1732.

>
> http://www.cryptographic.co.uk/factorise.html

Og den virker også med (visse versioner af) Netscape.

--
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)

---

"Jeppe Stig Nielsen" <mail@jeppesn.dk> skrev i en meddelelse
news:3CB1E90B.100C97F3@jeppesn.dk...
> "Jens Axel Søgaard" wrote:
> >
> > Jeg har fundet et lille Java-program, som kan faktorisere alle
> > de tal, du har brug for. De har endda en liste med historiske
> > eksempler.
>
> Der er jo også tallet F5 = 2^(2^5)+1 = 4.294.967.297 faktoriseret af
> Euler i 1732.

Som altid dukker op som opgave, men desværre sjældent med tilhørende
forklaring.

--
Jens Axel

---

"Jens Axel Søgaard" wrote:
>
> > Der er jo også tallet F5 = 2^(2^5)+1 = 4.294.967.297 faktoriseret af
> > Euler i 1732.
>
> Som altid dukker op som opgave, men desværre sjældent med tilhørende
> forklaring.

Forklaringen er at Euler indså at en faktor i Fm = 2^(2^m)+1 nød-
vendigvis må være af typen k·2^n+1 hvor n er større eller lig med m+2.

I tilfældet F5 må en faktor være af formen k·2^7+1 hvor k evt. kan
være et lige tal.
Altså skal faktorer søges blandt

129
257
385
513
641
769
etc.

Imidlertid er ikke alle disse tal primtal, og derfor har de mindre
faktorer som ikke er af den rigtige form.

De eneste kandidater der så er tilbage, er 257, 641, 769, ...

Dem må man så prøve én efter én. 641 viser sig at virke.

--
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)

---

"Jeppe Stig Nielsen" <mail@jeppesn.dk> skrev i en meddelelse
news:3CB2C835.1295E8E@jeppesn.dk...
> "Jens Axel Søgaard" wrote:
> >
> > > Der er jo også tallet F5 = 2^(2^5)+1 = 4.294.967.297 faktoriseret af
> > > Euler i 1732.
> >
> > Som altid dukker op som opgave, men desværre sjældent med tilhørende
> > forklaring.
>
> Forklaringen er at Euler indså at en faktor i Fm = 2^(2^m)+1 nød-
> vendigvis må være af typen k·2^n+1 hvor n er større eller lig med m+2.

Ja - men det historiske aspekt, nemlig at eksemplet blev brugt til at
skyde hypotesen "Fm er et primtal" kommer sjældent med.
Allenby er dog en undtagelse.

Jeg synes opgaven bliver sjovere, når man får det historiske vingesus med.

--
Jens Axel

---

"Jens Axel Søgaard" wrote:
>
> Ja - men det historiske aspekt, nemlig at eksemplet blev brugt til at
> skyde hypotesen "Fm er et primtal" kommer sjældent med.
> Allenby er dog en undtagelse.
>
> Jeg synes opgaven bliver sjovere, når man får det historiske vingesus med.

Sandt nok.
Og man kan lige få med at i dag er hypotesen at Fm er sammensat for
alle m>4.

--
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)

---

Ole Kristensen wrote:
> Men jeg vil gerne finde en metode, så jeg kan finde svar på tilsvarende
> opgaver i fremtiden.

Den med primfaktorerne er et stort skridt på vejen. Et trin videre er
at hæfte sig ved at der kun er 7 cifre i resultatet. Det vil sige at den
ene faktor i multiplikationen må starte med et 1-tal, ellers vil
resultatet blive for stort. Det reducer mulighederne en hel del.

Nu har jeg så ikke taget mig tid til at finde yderlige udelukkelses-
muliheder, men det skal der nok være. På den måde kan bør det kunne lade
sig gøre at finde løsningen uden ret stort regnearbejde.

Men der er jo ikke nemt at lave en generel metode til at "opdage" sådanne
logiske slutninger. Det er derfor at det kan være sjovt at finde løsninger,
der undgår en masse regnearbejde.

Og nu bliver jeg altså "nødt" til at gøre lidt reklame for et "eventyr"
som jeg engang har skrevet, opbygget omkring en anden, og meget klassisk,
"regneopgave". Se http://home1.inet.tele.dk/sfromis/annie.html
Dér dyrker jeg flere forskellige løsnings strategier, med varierende
anvendelse af logik kontra regnekraft/kompleksitet.

Mvh. Johnnie

---

Johnnie Hougaard Nielsen skrev:

>Den med primfaktorerne er et stort skridt på vejen. Et trin videre er
>at hæfte sig ved at der kun er 7 cifre i resultatet. Det vil sige at den
>ene faktor i multiplikationen må starte med et 1-tal, ellers vil
>resultatet blive for stort.

2*4 er også en teoretisk mulighed. Jeg kan ikke lige se en
systematisk metode, men man kan indsnævre mulighederne ved at se
på de første cifre, og det sidste.

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

---

Bertel Lund Hansen wrote:
> >den ene faktor i multiplikationen må starte med et 1-tal, ellers vil
> >resultatet blive for stort.
>
> 2*4 er også en teoretisk mulighed.

Med de foreliggende cifre, nej, da de 2 første cifre af resultatet er givet
som 86. Efter udelukkelse af den trivielt ubrugelige mulighed at den ene
faktor simpelthen er 2, må det konstateres at de mindste faktorer startende
med 2 og 4 er 21 og 45, og så har vi allerede et 9-tal i første ciffer af
resultatet. Dutter ikke. Derefter er menteoverføring til mindst 8 cifre
uundgåelig.

Derfor holder der vand at første ciffer i den ene faktor *skal* være 1.

Mvh. Johnnie

---

Tak for alle indlæggene, selvom de fleste vist har glemt spørgsmålet ;-D

Men for at give lidt tilbage til gruppen, så har jeg løst opgaven:

Jeg har linet mulighederne op i et regneark og farvekodet dem dernedad
(udeladt de mest usandsynlige) og udregnet de 2 resultater.

Og fandt så at primtallene:
491x37x2 = 6874 og
37x17x2 = 1258

Løser spørgsmålet.

Og så er alle cifrene i talrækken 6 5 8 8 7 2 1 4 anvendt!


Jeg fik følgende input fra en engelsksproget list, hvor de er lidt mere
disciplinerede til at holde sig til emnet ;-D
---------
At first glance, I would break 8647492 into its prime numbers and then
iterate through the possible combinations until I would find 2 numbers that
would be composed of 6 5 8 8 7 2 1 4.

Example:
8647492 = 491*37*17*7*2*2, so when we iterate through the combinations we
would have:

(491*37*17*7*2*2) = 8647492 --> Nope!

(491*37*17*7*2)*(2) = 4323746 * 2 --> Nope!

(491*37*17*7)*(2*2) = 2161873 * 4 --> Nope!

(491*37*17*2)*(7*2) = 617678 * 14 --> Nope! . . . unless we can take numbers
more the once.

(491*37*17)*(7*2*2) = 308839 * 28 --> Nope!



Note: This is quite like not-ing binary numbers . . . for instance, the
second number could be thought of as (1*1*1*1*1*0)*(0*0*0*0*0*1) . . . where
each 1 represents the number to include and 0 indicates the number not to
include in the list of prime numbers [491, 37, 17, 7, 2, 2] . . . the second
"binary" looking thing is just the NOT of the first "binary" looking thing
------------------

Og endelig kan bidrage med koden, der spytter løsningen ud på et splitsekund
i computeren (skal selvfølgelig tilpasses diverse programmeringssprog:

numstr:="6 5 8 8 7 2 1 4"
product:=8647492

result:=[]
n:=INT(SQRT(product))
repeat with i:=1 to n
if MOD(product,i)=0 then
j:=product/i
c:=i^j
z:=CharCount(c)
t:=numstr
repeat with k:=1 to z
v:=Find(SubStr(c,k,k),t)
if v=0 then exit repeat
else
if k=z then AddLinear(result,[i,j])
else t:=ReplaceString(t,v,1,"")
end if
end repeat
end if
end repeat

Spytter2 resultater ud [[1258, 6874}}- hvilket er svaret på talgåden!

Med venlig hilsen

Ole Kristensen

---

Ole Kristensen wrote:
> break 8647492 into its prime numbers and then
> iterate through the possible combinations until

Jamen, det er jo primitivt, bare at prøve alle mulighederne igennem.

Det bliver da først sjovt når problemet kan løses uden en masse
regnearbejde, også selv om computeren er i stand til at klare det i
et ruf.

At det så godt kan tænkes at tage længere til at tænke elegante tanker,
end at programmere en simplistisk teknik, er så en anden sag.

Forresten - fint at du vender tilbage med en opfølgning.

Mvh. Johnnie

---

Claus Rasmussen <clr@cc-consult.dk> writes:

> Det er for i øvrigt dét, der gør vores krypteringsalgoritmer
> så sikre som de er. Kunne man primtalsfaktorisere på en hurtigere
> måde, ville man nemt kunne bryde koderne i kryptering.

Det er ikke alle krypteringsalgoritmer der baserer sig på at
primtalsfaktorisering er svært. Det er endnu uvidst om faktorisering
af primtal er NP-hårdt.

Jeg mener hverken at DiffieHellman eller Elgamal er baseret på
primtalsfaktorisering på samme måde som RSA. Elgamal er i hvertfald
baseret på diskrete logaritmer som jeg ikke mener at en effektiv
primtalsfaktorisering nødvendigvis vil gavne noget som helst.

--
Emacs er det eneste moderne styresystem der ikke er multitrådet.

---

Peter Makholm wrote:

> Det er ikke alle krypteringsalgoritmer der baserer sig på at
> primtalsfaktorisering er svært. Det er endnu uvidst om faktorisering
> af primtal er NP-hårdt.

Jeg mener at have hørt (på slashdot) at primtalsfaktorisering var
noget, man kunne bruge kvantekomputere til, mens samme kvantekomputere
ikke ville kunne gøre noget ved NP-hårde problemer. Ergo...

I øvrigt: Det hedder "primtalsfaktorisering" og ikke "faktorisering
af primtal". Bill Gates er engang kommet til at sige noget lignende
og der findes masser af folk på nettet, der har dén udtalelse i deres
signatur.

Det kunne være, jeg skulle sende en CC til Allan Olesen


> Jeg mener hverken at DiffieHellman eller Elgamal er baseret på
> primtalsfaktorisering på samme måde som RSA. Elgamal er i hvertfald
> baseret på diskrete logaritmer som jeg ikke mener at en effektiv
> primtalsfaktorisering nødvendigvis vil gavne noget som helst.

Det har du vist ret i.

-Claus

---

Claus Rasmussen <clr@cc-consult.dk> writes:

> Peter Makholm wrote:
>
> > Det er ikke alle krypteringsalgoritmer der baserer sig på at
> > primtalsfaktorisering er svært. Det er endnu uvidst om faktorisering
> > af primtal er NP-hårdt.
>
> Jeg mener at have hørt (på slashdot) at primtalsfaktorisering var
> noget, man kunne bruge kvantekomputere til, mens samme kvantekomputere
> ikke ville kunne gøre noget ved NP-hårde problemer. Ergo...

Kvantecomputere kan faktorisere. Det vides ikke om faktorisering kan
bruges til at løse NP hårde problemer. PRIMENESS og COMPOSITENESS
problemerne er begge i NP (og da de er komplementære derfor begge også
i coNP) men vides ikke at være NP hårde. NP er en klasse af problemer
med ja/nej svar, ikke hvor svaret er en række primtal, så det er det
nærmeste man kommer faktorisering i NP.

Man har ikke fundet nogen måde at bruge kvantecomputere til at løse et
bevist NP-hårdt problem.

Vi *ved* ikke om kvantecomputere kan løse NP-fuldstændige problemer,
da vi ikke ved om P=NP, men indtil videre ser det ikke sådan ud.

Hvis man kunne vise at en kvantecomputer kunne løse en ægte delmængde
af NP-problemerne, så ville man vide at P!=NP, og det ville være stort!

Hvis man kunne vise at en kvantecomputer kunne løse alle NP problemer,
så ville det ikke betyder at P=NP, men at NP ikke var så god en klasse
at tage svært-inverterbare funktioner til kryptografi fra.

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'

---

Lasse Reichstein Nielsen wrote:
>
> Man har ikke fundet nogen måde at bruge kvantecomputere til at løse et
> bevist NP-hårdt problem.

.... i polynomiel tid!


> Vi *ved* ikke om kvantecomputere kan løse NP-fuldstændige problemer,
> da vi ikke ved om P=NP, men indtil videre ser det ikke sådan ud.

Det er klart at P=NP medfører at NP er en delmængde af BQP. Men hvordan
kan man sige noget om sammenhængen mellem NP og BQP hvis man ved at
P!=NP ?

--
mvh. Karsten Strandgaard Jørgensen - http://www.hammerich.cjb.net
"I call upon our Staffordshire delegate to explain this weird behaviour"

---

Scripsit Karsten S. Jørgensen <karsten@daimi.au.dk>

> Det er klart at P=NP medfører at NP er en delmængde af BQP.

Hvad er BQP? Q=Quantum?

--
Henning Makholm "I Guds Faders namn, och Sonens, och den Helige
Andes! Bevara oss från djävulens verk och från Muhammeds,
den förbannades, illfundigheter! Med dig är det värre än med
någon annan, ty att lyssna till Muhammed är det värsta av allt."

---

Henning Makholm wrote:
>
> Scripsit Karsten S. Jørgensen <karsten@daimi.au.dk>
>
> > Det er klart at P=NP medfører at NP er en delmængde af BQP.
>
> Hvad er BQP? Q=Quantum?

BQP er (skrevet ud fra hukommelsen): klassen af problemer, der kan løses
i poly-tid af en kvante-Turingmaskine med fejl i højst 1/3 af tilfældene
(for alle mulige inputs).

Et gæt på forkortelsen BQP kunne være:
Bounded error probability in Quantum Polynomial time
--
mvh. Karsten Strandgaard Jørgensen - http://www.hammerich.cjb.net
"I call upon our Staffordshire delegate to explain this weird behaviour"

---

Karsten S. Jørgensen <karsten@daimi.au.dk> writes:

> Lasse Reichstein Nielsen wrote:
> >
> > Man har ikke fundet nogen måde at bruge kvantecomputere til at løse et
> > bevist NP-hårdt problem.
>
> ... i polynomiel tid!

Naturligvis :).

> > Vi *ved* ikke om kvantecomputere kan løse NP-fuldstændige problemer,
> > da vi ikke ved om P=NP, men indtil videre ser det ikke sådan ud.
>
> Det er klart at P=NP medfører at NP er en delmængde af BQP. Men hvordan
> kan man sige noget om sammenhængen mellem NP og BQP hvis man ved at
> P!=NP ?

Ikke noget direkte, jeg var ikke særlig præcis her :)
Vi ved at P er indeholdt i BQP som er indeholdt i NP, men vi ved ikke
at nogen af inklusionerne er ægte eller uægte.
/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'

---

Lasse Reichstein Nielsen wrote:
>
> Karsten S. Jørgensen <karsten@daimi.au.dk> writes:
>
> > > Vi *ved* ikke om kvantecomputere kan løse NP-fuldstændige problemer,
> > > da vi ikke ved om P=NP, men indtil videre ser det ikke sådan ud.
> >
> > Det er klart at P=NP medfører at NP er en delmængde af BQP. Men hvordan
> > kan man sige noget om sammenhængen mellem NP og BQP hvis man ved at
> > P!=NP ?
>
> Ikke noget direkte, jeg var ikke særlig præcis her :)
> Vi ved at P er indeholdt i BQP som er indeholdt i NP, men vi ved ikke
> at nogen af inklusionerne er ægte eller uægte.

Nå? Ved man at BQP er indeholdt i NP? Det er nyt for mig. Jeg husker det
således:
Bevist: P < BPP < BQP < PSPACE
Bevist: P < NP < PSPACE
Formodet: NP !< BQP
Formodet: BQP !< NP
(hvor "<" skal forestille "indeholdt i"-tegnet)

--
mvh. Karsten Strandgaard Jørgensen - http://www.hammerich.cjb.net
"I call upon our Staffordshire delegate to explain this weird behaviour"

---

Karsten S. Jørgensen <karsten@daimi.au.dk> writes:

> Nå? Ved man at BQP er indeholdt i NP? Det er nyt for mig. Jeg husker det
> således:
> Bevist: P < BPP < BQP < PSPACE
> Bevist: P < NP < PSPACE
> Formodet: NP !< BQP
> Formodet: BQP !< NP
> (hvor "<" skal forestille "indeholdt i"-tegnet)

Det kan være at jeg forveksler BQP med QP, og det er også nogle år
siden jeg hørte noget sidst. Lidt søgning giver da også at man ikke
ved om NP er i BQP, og vist også at der er et problem i QP som ikke er
i hverken NP eller coNP (men jeg kunne ikke finde siden igen :).
Så tak for opdateringen :)

/L
--
Lasse Reichstein Nielsen - lrn@hotpop.com
'Faith without judgment merely degrades the spirit divine.'

---

Claus Rasmussen <clr@cc-consult.dk> wrote:

>Det kunne være, jeg skulle sende en CC til Allan Olesen

Jeg bærer skam ikke nag over, at Peter har postet et 4-cifret
antal indlæg med mit citat i signaturen.


--
Allan Olesen, Lunderskov.
Danske musikere tjener penge ved ulovlig softwarekopiering.

---

Allan Olesen wrote:

> Claus Rasmussen <clr@cc-consult.dk> wrote:
>
>> Det kunne være, jeg skulle sende en CC til Allan Olesen
>
> Jeg bærer skam ikke nag over, at Peter har postet et 4-cifret
> antal indlæg med mit citat i signaturen.

Arh, nu ikke så fjalet. Du vil bare ikke indrømme, at du faktisk er
stolt over din prominente placering på google:

http://www.google.com/search?hl=en&q=n%F8rd+undskyldende

Det er der mange, der vil misunde dig

-Claus

---

Claus Rasmussen <clr@cc-consult.dk> wrote:

>Arh, nu ikke så fjalet. Du vil bare ikke indrømme, at du faktisk er
>stolt over din prominente placering på google:

Jeg er ved at revne...


--
Allan Olesen, Lunderskov.
Danske musikere tjener penge ved ulovlig softwarekopiering.

---

Claus Rasmussen <clr@cc-consult.dk> writes:

> I øvrigt: Det hedder "primtalsfaktorisering" og ikke "faktorisering
> af primtal". Bill Gates er engang kommet til at sige noget lignende

Så meget for at forsøge sig med et varieret sprog. Jeg tror endda selv
jeg har moret mig over BG's udtalelser på et tidspunkt.

--
Emacs er det eneste moderne styresystem der ikke er multitrådet.

---

Allan Olesen <aolesen@post3.tele.dk> writes:

> Jeg bærer skam ikke nag over, at Peter har postet et 4-cifret
> antal indlæg med mit citat i signaturen.

1050 på Usenet og Debians maillinglister er hvad google kan
finde. Hvilket selvfølgeligt er en smule mere en dobbelt så mange
gange som du citerede Lars Fischer over en noget længere periode.

Du er bare jaloux over er den findes sølle 4 gange på den rigtige
Google.

--
Emacs er det eneste moderne styresystem der ikke er multitrådet.

---

"Peter Makholm" <peter@makholm.net> skrev i en meddelelse
news:873cy4dbof.fsf@xyzzy.adsl.dk...
> Allan Olesen <aolesen@post3.tele.dk> writes:
>
> > Jeg bærer skam ikke nag over, at Peter har postet et 4-cifret
> > antal indlæg med mit citat i signaturen.
>
> 1050 på Usenet og Debians maillinglister er hvad google kan
> finde. Hvilket selvfølgeligt er en smule mere en dobbelt så mange
> gange som du citerede Lars Fischer over en noget længere periode.

Men Allan fik da lov:

http://www.jasoegaard.dk/laml/link/show_link.laml?linkid=42

Hvad man ikke kan finde på Google ...

--
Jens Axel

---

"Jens Axel Søgaard" <usenet@soegaard.net> writes:

> Men Allan fik da lov:

Det fik jeg også, men jeg spurgte per email med message-id
<878zggtgch.fsf@xyzzy.adsl.dk>. (Og skulle vi så ikke stoppe den
deltråd. Den er ikke helt on-topic)

--
Emacs er det eneste moderne styresystem der ikke er multitrådet.