SNP (күрделілігі) - SNP (complexity) - Wikipedia

Жылы есептеу күрделілігі теориясы, SNP (бастап.) Қатаң NP) Бұл күрделілік сыныбы құрамында шектеулі ішкі жиын бар NP тұрғысынан оның логикалық сипаттамасына негізделген графикалық-теориялық қасиеттері. Ол сыныпты анықтауға негіз болады MaxSNP туралы оңтайландыру мәселелері.

Қасиеттері болып табылатын есептер класы ретінде анықталады реляциялық құрылымдар (сияқты графиктер ) а екінші ретті логика келесі формула:

,

қайда құрылымның қатынастары (график үшін іргелес қатынас сияқты), белгісіз қатынастар (шыңдар кортеждерінің жиынтығы), және - бұл кванторсыз формула: қатынастардың кез-келген бульдік тіркесімі.[1] Яғни, экзистенциалды екінші ретті сандық қатынасқа ғана рұқсат етіледі (тек шыңдарға) әмбебап бірінші ретті кванттауға, егер шыңдар бойынша экзистенциалдық кванттауға жол берілсе, нәтижесінде алынған күрделілік сыныбы NP-ге тең болады (дәлірек айтсақ) , қатынастық құрылымдардың қасиеттерінің класы, олар NP-де), факт ретінде белгілі Фагин теоремасы.

Мысалы, SNP құрамында 3-бояу бар (берілген графиктің бар-жоғын анықтау мәселесі 3 түсті ), өйткені оны келесі формула арқылы көрсетуге болады:

.

Мұнда жиынтықтарды (бірыңғай қатынастар), ал кіріс графиктің көршілестік қатынасын білдіреді үш түстің біреуімен боялған шыңдар жиынтығына сәйкес келеді, SNP құрамында да к-SAT мәселесі: логикалық қанағаттанушылық проблемасы (SAT), онда формула шектелген конъюнктивті қалыпты форма және ең көп дегенде к бір тармаққа арналған литералдар, қайда к бекітілген

MaxSNP

Ұқсас анықтама қарастырады оңтайландыру мәселелері, формуланы қанағаттандырудың орнына барлық кортеждер, ол қанағаттандырылған кортеждердің санын көбейтуді қалайды. MaxSNP0 келесі формада көрінетін реляциялық құрылымдар бойынша оңтайландыру есептерінің класы ретінде анықталады:

MaxSNP содан кейін барлық мәселелердің класы ретінде анықталады L-редукция (сызықтық редукция, емес кеңістікті азайту) мәселелеріне MaxSNP0.[2]Мысалға, MAX-3SAT проблема болып табылады MaxSNP0: 3-CNF-SAT данасы берілген ( логикалық қанағаттанушылық проблемасы формуласымен бірге конъюнктивті қалыпты форма және бір тармаққа ең көп дегенде 3 литр), мүмкіндігінше көбірек сөйлемді қанағаттандыратын тапсырма табыңыз. толық проблема MaxSNP.

Белгіленген коэффициент бар жуықтау алгоритмі кез келген мәселені шешу үшін MaxSNP, демек MaxSNP ішінде орналасқан APX, қандай да бір тұрақты қатынаста болатын барлық есептер класы. Шын мәнінде жабылу MaxSNP астында PTAS қысқартулары (L-редукцияларға қарағанда сәл жалпы) -ге тең APX; яғни, кез-келген мәселе APX бар PTAS қысқарту оған кейбір проблемалардан MaxSNP. Атап айтқанда, әрқайсысы MaxSNP- толық проблема (L-төмендетулер бойынша немесе астында AP төмендету ) сонымен қатар APX- толық (PTAS қысқартуларына сәйкес), демек PTAS қабылдамайды, егер P = NP. Алайда, мұның дәлелі мынаған сүйенеді PCP теоремасы, ал дәлелі MaxSNP-толықтылық көбінесе қарапайым болып келеді.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Федер, Томас; Варди, Моше Ю. (1993). «Монотонды монадты SNP және шектеулі қанағаттану». Есептеулер теориясы бойынша жиырма бесінші ACM симпозиумының материалдары. дои:10.1145/167088.167245.
  2. ^ Пападимитриу, Христос Х.; Яннакакис, Михалис (1991). «Оңтайландыру, жуықтау және күрделілік сыныптары». Дж. Компут. Сист. Ғылыми. 43 (3): 425–440. Zbl  0765.68036.

Сыртқы сілтемелер