Re: Czyżby NP=P ?! - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › Czyżby NP=P ?! › Re: Czyżby NP=P ?!

X-Received: by 2002:a05:620a:13fa:: with SMTP id h26mr10883292qkl.150.1579712531322;
Wed, 22 Jan 2020 09:02:11 -0800 (PST)
X-Received: by 2002:a05:620a:13fa:: with SMTP id h26mr10883292qkl.150.1579712531322;
Wed, 22 Jan 2020 09:02:11 -0800 (PST)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erj
e.net!feeder.erje.net!news.uzoreto.com!news.dns-netz.com!news.freedyn.net!newsf
eed.xs4all.nl!newsfeed9.news.xs4all.nl!tr2.eu1.usenetexpress.com!feeder.usenete
xpress.com!tr2.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.gigan
ews.com!g89no11174807qtd.0!news-out.google.com!w29ni12qtc.0!nntp.google.com!g89
no11174797qtd.0!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Wed, 22 Jan 2020 09:02:11 -0800 (PST)
In-Reply-To: <5e279ddd$0$547$65785112@news.neostrada.pl>
Complaints-To: g...@g...com
Injection-Info: google-groups.googlegroups.com;
posting-host=2001:6a0:5001:3:bdc1:da28:a6e5:b564;
posting-account=CvUQzQoAAABvVQmR58QmR6N4Cev1qhAS
NNTP-Posting-Host: 2001:6a0:5001:3:bdc1:da28:a6e5:b564
References: <5e279ddd$0$547$65785112@news.neostrada.pl>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <f...@g...com>
Subject: Re: Czyżby NP=P ?!
From: bartekltg <b...@g...com>
Injection-Date: Wed, 22 Jan 2020 17:02:11 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 27
Xref: news-archive.icm.edu.pl pl.comp.programming:214707
[ ukryj nagłówki ]

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