NP-максималды дәрежелі планарлы графиктерге арналған Бақыланатын қойылған міндеттің толықтығы 3?

Мен NP-ның үстемдік мәселелерін толықтай дәлелдеу үшін қолданылатын кейбір әдістер туралы білуге ​​тырысамын. NP-complet деп аталатын мәселелердің бірі - максимум 3 (Гарей және Джонсон) бар планарлы графиктердің үстемдік саны. Барлығы қағаздар мен кітаптарда Гарей және Джонсонның кітабына сілтеме жасайды, бірақ ешқандай дәлел жоқ, себебі Гарей және Джонсонның кітабында жарияланбаған кітаптың соңында сілтеме бар.

Кез-келген дене осы мәселені дәлелдейтін не оған қандай да бір сілтеме екенін біле ме?

Рахмет, Элхам

5
Гамильтондық циклдің проблемасынан максимальді градусқа ие планарлы графиктерде жылдам төмендеу бар. 3, бірақ сіз планарлы 3-SAT-ден тікелей бастай аласыз
қосылды автор Marzio De Biasi, көзі
Планшеттік 3SAT-ден тікелей азайту үшін бірге қайнату керек ингредиенттер болып табылады: оң/теріс айнымалы гаджеттер, сымдар, сым бөлу, OR гаджеттер, сөйлемдер шыңдары. Әрбір бөлік/гаджет ең үстем шыңдардың ең аз белгіленген санын талап етуі керек. Бұл суретте сымды және OR гаджетін енгізудің ықтимал жолы көрсетілген . Бұл зерттеу деңгейінің сұрағы емес, сондықтан оны белгілеп, cs.stackexchange.com сайтына жылжытуды сұраңыз және мен бұл түсініктемеге толығырақ жауап бере аламын.
қосылды автор Marzio De Biasi, көзі
Мен дәлелді білмеймін, бірақ кейбір ұғымдар: 1. Гари мен Джонсон әдетте қандай проблеманы пайдалану туралы айтады (сілтеме - жеке қарым-қатынас болса ...). 2. Планшеттік шыңы немесе 3-SAT жазықтықты пайдалану қиын, бұл менің басымның жоғарғы жағында. 3. Бұны қалай қолдануға болады, егер сіз TCS-те не сізде не болып жатқанын дәлелдейтін болсаңыз деп ойлайсыз ба? 4. Сіз не істегеніңіз туралы айтпағандықтан (қандай проблемадан бас тартқыңыз келді, бірақ сіз сәтсіздікке ұшырадысыз). Сіздің сұрағыңыз зерттеу деңгейі емес және көп немесе аз үй тапсырмасына ұқсайды деп ойлаймын.
қосылды автор Saeed, көзі
@ Мұхаммед әл-Түркістани, Бұл басқа мәселе, ал бұл фактіні (теореманы) пайдалану арқылы Джукамен екіншісін дәлелдеді (нөлден емес), ол басқа жолмен жұмыс істемейді.
қосылды автор Saeed, көзі
@ Marzio De Biasi, Сізге көп рахмет Marzio, мен шынымен оқу тобына арналған жауап қажет, мен күрделі заттар туралы біле бастадым және NP толықтығын дәлелдеуді оқыдым. Жарайды, мен оны cs.stackexchange.com сайтына апарамын. Бірақ, мен дәлелдеме қағазда көрсетілген: «T. Kikuno, N. Yoshida және Y. Kakuda.НП - текше планарлы графиктердегі басым мәселенің толықтығы Электроника және байланыс институтының мәмілелері Жапония инженерлері, E63 (6): 443-444, 1980. « Құрметпен, Элхам
қосылды автор Daniel Hilgarth, көзі

Жауап жоқ

0