fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Tudományok » Természettudományok » Hogyan kell a MAXFTN problémát...

Hogyan kell a MAXFTN problémát visszavezetni a 3SZÍN problémára?

Figyelt kérdés

[link]

198. oldalon található ez alapján.

Azt nem értem, hogy a bizonyítás ami ott szerepel, miért bizonyítja, hogy visszavezethető. A lépéseket értem, azt nem, hogy ez miért igazolja.


3SZÍN: Input: G(V,E) Output: igen: ha G 3színezhető

MAXFTN Input: G(V,E), k Output: igen: ha G-ben van k méretű független ponthalmaz.



#probléma #algoritmus #SAT #polinom #visszavezetés #bonyolultságelmélet #NP-teljes #döntési probléma #NP-nehéz #Karp-redukció
2019. jan. 2. 16:09
 1/3 anonim ***** válasza:
0%
Bmemézz inkább, mindenki jobban jár.
2019. jan. 2. 18:45
Hasznos számodra ez a válasz?
 2/3 A kérdező kommentje:
Topkek.
2019. jan. 2. 23:18
 3/3 anonim ***** válasza:

Ez a 3SZÍN-t vezeti vissza a MAXFTN-re, nem pedig fordítva. 3SZÍN(G) = MAXFTN(G', |G|) ahol G' három, páronként összekötötgetett G-klónból áll. Ezzel bizonyítja, hogy MAXFTN NP-teljes, így felesleges erőlködni könnyebb megoldás keresésén.

Hiszen ha létezne könnyű megoldás MAXFTN-re, akkor létezne 3SZÍN-re is: MAXFTN-be bedobhatnánk a pimpelt G' gráfot és G csúcsszámát. 3SZÍN-ről viszont tudjuk, és korábban bizonyítottuk, hogy NP-teljes, így MAXFTN se lehet más.

2019. jan. 3. 16:26
Hasznos számodra ez a válasz?

Kapcsolódó kérdések:

Tudományok főkategória kérdései »
Tudományok - Természettudományok kategória kérdései »




Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!