Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #33741

Re: Czyżby NP=P ?!

Show all headers | View raw

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¼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∑Nj¼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_Combinatorial_optimization_by_simulating_adiabatic_bifurcations_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

Back to pl.comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Czyżby NP=P ?! Borneq <borneq@antyspam.hidden.pl> - 2020-01-22 01:57 +0100
  Re: Czyżby NP=P ?! "M.M." <mmarszik@gmail.com> - 2020-01-21 17:21 -0800
    Re: Czyżby NP=P ?! Borneq <borneq@antyspam.hidden.pl> - 2020-01-22 02:34 +0100
      Re: Czyżby NP=P ?! slawek <x.y@org.org> - 2020-01-23 21:27 +0100
  Re: Czyżby NP=P ?! Wojciech Muła <wojtek.mula@gmail.com> - 2020-01-22 03:34 -0800
  Re: Czyżby NP=P ?! bartekltg <bartekltg@gmail.com> - 2020-01-22 09:02 -0800
    Re: Czyżby NP=P ?! "M.M." <mmarszik@gmail.com> - 2020-01-23 20:42 -0800

csiph-web