eGospodarka.pl

eGospodarka.plGrupypl.comp.programming › Czyżby NP=P ?!
Ilość wypowiedzi w tym wątku: 6

  • 1. Data: 2020-01-22 01:57:00
    Temat: Czyżby NP=P ?!
    Od: Borneq <b...@a...hidden.pl>

    Być może nawet gdy się równa, to może być nieopłacalne, gdy n będzie
    równe np. milion, wtedy x^n będzie wolniejsze dla początkowych danych
    niż 2^x.

    Ale..

    "
    Toshiba stworzyła algorytm, który ma wyprzedzać komputery kwantowe
    oshiba twierdzi, że udało im się stworzyć algorytm, który wyprzedza
    komputery kwantowe przy wykorzystaniu standardowego hardware'u. Firma ma
    zamiar skomercjalizować swoje rozwiązanie.

    Przed rynkiem komputerowym stoi ogromne wyzwanie. Powoli zbliżamy się do
    kresu możliwości tradycyjnego krzemu. Wkrótce (jest to prawdopodobnie
    kwestia kilku lat) zwiększenie wydajność PC-tów będzie ogromnym
    wyzwaniem. Tymczasem na świecie jest coraz więcej danych, które trzeba
    przetwarzać i analizować. Komputery radzą sobie z tym coraz gorzej i
    stąd duża wiara w komputery kwantowe, które miałyby rozwiązać wiele
    dzisiejszych problemów. Tymczasem Toshiba twierdzi, że znalazła inny sposób.

    Japońska firma od kilku lat miała pracować i doskonalić algorytm do
    przetwarzania i analizowania dużych ilości danych. SBA (Simulated
    Bifurcation Algorithm) w końcu jest gotowy i efekty są ponoć bardzo
    zaskakujące. Zdaniem przedstawicieli Toshiby radzi on sobie lepiej niż
    rozwiązania stosowane w najszybszych superkomputerach, a nawet
    komputerach kwantowych. W trakcie demonstracji pokazano, jak algorytm
    znajduje się rozwiązanie dla problemu z 2000 połączonych zmiennych w
    zaledwie 50 mikrosekund. To mniej więcej 10 raczy szybciej niż oparte na
    laserach komputery kwantowe.

    Chociaż nad komputerami kwantowymi pracują największe firmy
    technologiczne na świecie, to wciąż efekty nie zadowalają. Powstały już
    co prawda pierwsze urządzenia, ale są one bardzo ograniczone i pod
    względem wydajności daleko im do tego, co byłoby wymagane w praktyce.
    Dlatego algorytm Toshiby może być pewnego rodzaju rewolucją. Czas
    pokaże, co z tego wyjdzie.
    "
    https://gamingsociety.pl/artykul/toshiba-simulated-b
    ifurcation-algorithm-1099121/


  • 2. Data: 2020-01-22 02:21:58
    Temat: Re: Czyżby NP=P ?!
    Od: "M.M." <m...@g...com>

    On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
    > Być może nawet gdy się równa, to może być nieopłacalne, gdy n będzie
    > równe np. milion, wtedy x^n będzie wolniejsze dla początkowych danych
    > niż 2^x.
    >
    > Ale..
    >
    > "
    > Toshiba stworzyła algorytm, który ma wyprzedzać komputery kwantowe
    > oshiba twierdzi, że udało im się stworzyć algorytm, który wyprzedza
    > komputery kwantowe przy wykorzystaniu standardowego hardware'u. Firma ma
    > zamiar skomercjalizować swoje rozwiązanie.
    >
    > Przed rynkiem komputerowym stoi ogromne wyzwanie. Powoli zbliżamy się do
    > kresu możliwości tradycyjnego krzemu. Wkrótce (jest to prawdopodobnie
    > kwestia kilku lat) zwiększenie wydajność PC-tów będzie ogromnym
    > wyzwaniem. Tymczasem na świecie jest coraz więcej danych, które trzeba
    > przetwarzać i analizować. Komputery radzą sobie z tym coraz gorzej i
    > stąd duża wiara w komputery kwantowe, które miałyby rozwiązać wiele
    > dzisiejszych problemów. Tymczasem Toshiba twierdzi, że znalazła inny sposób.
    >
    > Japońska firma od kilku lat miała pracować i doskonalić algorytm do
    > przetwarzania i analizowania dużych ilości danych. SBA (Simulated
    > Bifurcation Algorithm) w końcu jest gotowy i efekty są ponoć bardzo
    > zaskakujące. Zdaniem przedstawicieli Toshiby radzi on sobie lepiej niż
    > rozwiązania stosowane w najszybszych superkomputerach, a nawet
    > komputerach kwantowych. W trakcie demonstracji pokazano, jak algorytm
    > znajduje się rozwiązanie dla problemu z 2000 połączonych zmiennych w
    > zaledwie 50 mikrosekund. To mniej więcej 10 raczy szybciej niż oparte na
    > laserach komputery kwantowe.
    >
    > Chociaż nad komputerami kwantowymi pracują największe firmy
    > technologiczne na świecie, to wciąż efekty nie zadowalają. Powstały już
    > co prawda pierwsze urządzenia, ale są one bardzo ograniczone i pod
    > względem wydajności daleko im do tego, co byłoby wymagane w praktyce.
    > Dlatego algorytm Toshiby może być pewnego rodzaju rewolucją. Czas
    > pokaże, co z tego wyjdzie.
    > "
    > https://gamingsociety.pl/artykul/toshiba-simulated-b
    ifurcation-algorithm-1099121/

    Tyle znalazłem na wiki:

    https://pl.wikipedia.org/wiki/Bifurkacja_(matematyka
    )

    Gdzie można coś więcej doczytać na temat samej teorii?

    Pozdrawiam


  • 3. Data: 2020-01-22 02:34:48
    Temat: Re: Czyżby NP=P ?!
    Od: Borneq <b...@a...hidden.pl>

    On 1/22/20 2:21 AM, M.M. wrote:
    > Gdzie można coś więcej doczytać na temat samej teorii?

    Fraktale i chaos, choćby książka którą kupiłem jeszcze na studiach:

    Fraktale i chaos (ta mała książka) - Jacek Kudrewicz
    Fraktale. Granice chaosu (Ta duża ksiażka)- H.-O.Peitgen, H.Jurgens,
    D.Saupe (rok 1995)


    Ciekawe, może teoria bifurkacji była by przydatna do utrzymywania plazmy
    w Tokamaku? A ostatnio z Chin były wiadomości o sukcesach...


  • 4. Data: 2020-01-22 12:34:59
    Temat: Re: Czyżby NP=P ?!
    Od: Wojciech Muła <w...@g...com>

    On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
    > Być może nawet gdy się równa, to może być nieopłacalne, gdy n będzie
    > równe np. milion, wtedy x^n będzie wolniejsze dla początkowych danych
    > niż 2^x.
    >
    > Ale..
    >
    > "
    > Toshiba stworzyła algorytm, który ma wyprzedzać komputery kwantowe
    > oshiba twierdzi, że udało im się stworzyć algorytm, który wyprzedza
    > komputery kwantowe przy wykorzystaniu standardowego hardware'u. Firma ma
    > zamiar skomercjalizować swoje rozwiązanie.
    >
    > Przed rynkiem komputerowym stoi ogromne wyzwanie. Powoli zbliżamy się do
    > kresu możliwości tradycyjnego krzemu. Wkrótce (jest to prawdopodobnie
    > kwestia kilku lat) zwiększenie wydajność PC-tów będzie ogromnym
    > wyzwaniem. Tymczasem na świecie jest coraz więcej danych, które trzeba
    > przetwarzać i analizować. Komputery radzą sobie z tym coraz gorzej i
    > stąd duża wiara w komputery kwantowe, które miałyby rozwiązać wiele
    > dzisiejszych problemów. Tymczasem Toshiba twierdzi, że znalazła inny sposób.
    >
    > Japońska firma od kilku lat miała pracować i doskonalić algorytm do
    > przetwarzania i analizowania dużych ilości danych. SBA (Simulated
    > Bifurcation Algorithm) w końcu jest gotowy i efekty są ponoć bardzo
    > zaskakujące. Zdaniem przedstawicieli Toshiby radzi on sobie lepiej niż
    > rozwiązania stosowane w najszybszych superkomputerach, a nawet
    > komputerach kwantowych. W trakcie demonstracji pokazano, jak algorytm
    > znajduje się rozwiązanie dla problemu z 2000 połączonych zmiennych w
    > zaledwie 50 mikrosekund. To mniej więcej 10 raczy szybciej niż oparte na
    > laserach komputery kwantowe.
    >
    > Chociaż nad komputerami kwantowymi pracują największe firmy
    > technologiczne na świecie, to wciąż efekty nie zadowalają. Powstały już
    > co prawda pierwsze urządzenia, ale są one bardzo ograniczone i pod
    > względem wydajności daleko im do tego, co byłoby wymagane w praktyce.
    > Dlatego algorytm Toshiby może być pewnego rodzaju rewolucją. Czas
    > pokaże, co z tego wyjdzie.
    > "
    > https://gamingsociety.pl/artykul/toshiba-simulated-b
    ifurcation-algorithm-1099121/

    https://phys.org/news/2019-04-toshiba-breakthrough-a
    lgorithm-world-fastest.html

    "Toshiba has solved these issues by developing a novel combinatorial optimization
    algorithm, the Simulated Bifurcation Algorithm. It is highly parallelizable, and can
    therefore easily speed up problem solving on standard digital computer through
    parallel computation. As current large-scale computational systems can be used as is,
    there is no need to install new equipment, making it easy to scale up at a low cost."

    w.


  • 5. Data: 2020-01-22 18:02:11
    Temat: Re: Czyżby NP=P ?!
    Od: bartekltg <b...@g...com>

    On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:

    > Ale..

    Żade ale. To nie ma nic wsplnego z N ?= NP.
    To algorytm probabilistyczny, przybliżony, aproksymacyjny...
    Komiwojadzera też mozęsz rozwiązać w czasie liniowym, tylko niedokładnie.
    pytanie czy P=NP dotyczy znajdowania ścisłego, optymalnego rozwiązania.
    Ale dla wielu rzeczywistych przpadków takie przybliżone
    rozwiązanie jest wystarczająco dobre.

    I tu zaproponowali takie przylizone rozwiązanie*) dla jakeigoś
    problemu kombinarytorycznego, coś z modelem Isinga.

    https://www.researchgate.net/publication/332535366_C
    ombinatorial_optimization_by_simulating_adiabatic_bi
    furcations_in_nonlinear_Hamiltonian_systems

    Porównują się do symulowanego wyzarzania i jakeigoś algorytmu
    zaprojektowanego pos isinga.

    *) kantowy w sumie daje to samo:)


    pzdr
    bartekltg


  • 6. Data: 2020-01-24 05:42:37
    Temat: Re: Czyżby NP=P ?!
    Od: "M.M." <m...@g...com>

    On Wednesday, January 22, 2020 at 6:02:12 PM UTC+1, bartekltg wrote:
    > On Wednesday, January 22, 2020 at 2:00:02 AM UTC+1, Borneq wrote:
    >
    > > Ale..
    >
    > Żade ale. To nie ma nic wsplnego z N ?= NP.
    > To algorytm probabilistyczny, przybliżony, aproksymacyjny...

    Chyba że w innym sensie niż klasycznym... Ale nie piszą też nic o tym, że
    ich algorytm jest aproksymacyjny.

    [
    These problemsare NOTORIOUSLY DIFFICULT because of combinatorial explosion (1,2).
    Thus,special-purpose hardware devices for these problems are expected to beuseful. In
    particular, "Ising machines"designed for finding a groundstate of the Ising spin
    model (3) have recently attracted much attentionbecause many combinatorial
    optimization problems CAN BE MAPPED tothe Ising problem (4), including
    very-large-scale integrated circuit de-sign (5), drug design (6), and financial
    portfolio management (7). Thesemachines have been developed by various approaches:
    quantum com-puters based on quantum annealing (8,9) or quantum adiabatic
    opti-mization (10-12) implemented with superconducting circuits (13,14),coherent
    Ising machines (CIMs) implemented with laser pulses (15-20),and Ising machines based
    on simulated annealing (SA) (1,21,22)im-plemented with digital circuits such as
    field-programmable gate arrays(FPGAs) (23-29).
    ]


    [
    In this challenge, intense research efforts are underway to pave alternative
    approaches for computing and information processing. Among them, Ising machines have
    been shown to offer viable solutions for important NP-hard problems such as MAX-CUT 6
    , protein folding 7 , and traveling salesman 8 , among others
    [9][10][11][12][13][14][15] . To this end, a variety of Ising machines have been
    demonstrated in effective spin systems of trapped atoms 16,17 , polariton condensates
    18 , superconducting circuits 19 , coupled oscillators [20][21][22] , nanophotonic
    waveguides [23][24][25] , randomly coupled lasers [26][27][28] , and time-multiplexed
    optical parametric oscillators 29,30
    ]

    Klasycznie/asymptotycznie też nie wierzę żeby NP=P na dowolnym rozmiarze, w
    łatwiej postawione wyzwania też nie dowierzam. Ale można szukać bardzo
    szybkich i w miarę dokładnych algorytmów dla problemów o ograniczonym rozmiarze.

    Tu też ciekawszy cytat:
    [
    Solving an all-to-all connected 2000-node MAX-CUTproblem by a single-FPGA SB
    machineFrom the advantages and properties of SB, we expect that SB will beuseful for
    approximately solving large-scale Ising or MAX-CUT prob-lems with dense connectivity
    as fast as possible. To check this expec-tation, we compare our SB machine with a
    state-of-the-art CIM (17,19),because this machine has achieved outstanding
    performance for theseproblems. For this comparison, we solved an all-to-all connected
    2000-node MAX-CUT problem named K2000,whichwassolvedbytheCIM(17,19).We implemented an
    SB-based 2000-spin Ising machine with a singleFPGA. The product-sum operation, ?Nj
    1/4 1Ji;jxj, in Eq. 8, which is the mostcomputation-intensive part in SB, is
    performed efficiently by massivelyparallel processing. Ji,jxjterms of up to 8192 are
    processed at a singleclock, which is about four times more than the total spins. See
    the Sup-plementary Materials for details.One of the main results in (17) is that the
    CIM reached a targetenergy given by the Goemans-Williamson semidefinite
    programming(GW-SDP) algorithm (17,38) in about 70 ms in the best case among100
    trials, which is about 50 times shorter than that by the SA highlytuned in (17). [The
    SA in (17,19) is very fast by putting all the elementsof the coupling matrix Jon a
    cache of a single core. Thus, parallel com-puting with multiple cores cannot
    accelerate the SA because of commu-nication overheads.] In comparison with this, our
    single-FPGA SBmachine reaches the GW-SDP value in only 58 ms even in the worst
    caseamong 100 trials, as shown in Fig. 2A.Anothermainresultin(17) is that the CIM
    took only 5 ms to obtainas good solutions (large cut values) as the highly tuned SA
    obtained in50 ms, where the cut value of the MAX-CUT problem is given
    by?EIsing2?14?Ni 1/4 1?Nj 1/4 1Ji;jwith Ising parameters (see the
    SupplementaryMaterials). Figure 2B shows that our SB machine takes only 0.5 ms to
    obtain better solutions on average than both the CIM in 5 ms and theSA in 50 ms.
    ]



    > Komiwojadzera też mozęsz rozwiązać w czasie liniowym, tylko niedokładnie.
    > pytanie czy P=NP dotyczy znajdowania ścisłego, optymalnego rozwiązania.
    > Ale dla wielu rzeczywistych przpadków takie przybliżone
    > rozwiązanie jest wystarczająco dobre.
    >
    > I tu zaproponowali takie przylizone rozwiązanie*) dla jakeigoś
    > problemu kombinarytorycznego, coś z modelem Isinga.
    >
    > https://www.researchgate.net/publication/332535366_C
    ombinatorial_optimization_by_simulating_adiabatic_bi
    furcations_in_nonlinear_Hamiltonian_systems
    >
    > Porównują się do symulowanego wyzarzania i jakeigoś algorytmu
    > zaprojektowanego pos isinga.

    Na to wygląda.


    > *) kantowy w sumie daje to samo:)


    Podali za dużo literatury pomocniczej jak na rozrywkę przy śniadaniu ;-)


    Pozdrawiam

strony : [ 1 ]



Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: