Év szerint Hónap szerint Ugrás a hónaphoz

Maróti Miklós: Bevezetés a CSP problémák algebrai elméletébe II

 iCal fájl letöltése
Szerda, 2. Április 2025, 10:10 - 11:10
Könnyű eldönteni egy gráfról hogy 2-színezhető, azaz a csúcsok piros és kék színnel kiszínezhető, hogy minden él különböző színű csúcsokat köt össze. 
Ismert viszont, hogy a 3-színezhetőség eldöntése NP-teljes, azaz van polinom idejű algoritmus amely le tudja ellenőrzini a megoldást, és minden hasonló probléma erre visszavezethető. 
A 2- illetve 3-színezhetőség úgy általánosítható, hogy egy rögzített célgráfba (K2 illetve K3 a fenti esetben) keresünk gráfhomomorfizmust. 
Ismert, hogy ha P nem egyenlő NP-vel, akkor vannak további közbülső bonyolultsági osztályok. 
A néhány éve bizonyított CSP dichotómia tétel azt mondja ki, hogy bármilyen gráfszínezési probléma P vagy NP-teljes, azaz közbülső bonyolultsági osztályok nem fordulhatnak elő a CSP problémáknál. 
A témában több mint 12 éve tartottam egy bevezető előadást egy konferencián, az ott hangzottakat szeretnem itt is elmondani, és kicsit beszélni az azt követő fejleményekről.

Vissza

JEvents v3.1.8 Stable   Copyright © 2006-2013