Комплекстік теорияда co NP толық проблемалары – co NP класындағы ең қиын мәселелер. Оларды шешу P≠co NP болған жағдайда полиномдық уақытта мүмкін емес.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Күрделілік теориясында, co NP-ге толық есептік мәселелер – бұл co NP-дегі ең қиын мәселелер, яғни co NP-дегі кез келген мәселені тек полиномиялық қосымша шығынмен кез келген co NP-ге толық есептік мәселенің арнайы жағдайы ретінде қайта формулиреуге болады. Егер P, co NP-ден өзгеше болса, онда co NP-ге толық есептердің барлығы полиномиалдық уақытта шешілмейді. Егер co NP-ге толық мәселені жылдам шешудің жолы болса, онда бұл алгоритм барлық co NP мәселелерін жылдам шешу үшін пайдаланылуы мүмкін. Әрбір co NP-ге толық мәселе NP-ге толық мәселенің толықтыруы болып табылады. NP және co NP-де кейбір мәселелер бар, мысалы, P немесе бүтін сандарды көбейткіштерге жіктеудегі барлық мәселелер. Дегенмен, жиынтықтардың тең екендігі белгісіз, бірақ теңсіздік болуы ықтимал деп саналады. Толығырақ co NP және NP-ге толық қараңыз. Фортуна 1979 жылы кез келген сирек тіл co NP-ге толық (немесе тіпті co NP-ге қиын) болса, онда P = NP мәселесі, Махани теоремасының маңызды негізі екенін көрсетті.
In complexity theory, computational problems that are co NP complete are those that are the hardest problems in co NP, in the sense that any problem in co NP can be reformulated as a special case of any co NP complete problem with only polynomial overhead. If P is different from co NP, then all of the co NP complete problems are not solvable in polynomial time. If there exists a way to solve a co NP complete problem quickly, then that algorithm can be used to solve all co NP problems quickly. Each co NP complete problem is the complement of an NP complete problem. There are some problems in both NP and co NP, for example all problems in P or integer factorization. However, it is not known if the sets are equal, although inequality is thought more likely. See co NP and NP complete for more details. Fortune showed in 1979 that if any sparse language is co NP complete (or even just co NP hard), then [[P = NP problem, a critical foundation for Mahaney's theorem.
Ресми анықтама
Шешім проблемасы C co NP-толық деп аталады, егер ол co NP класында болса және co NP класындағы әрбір проблема оған полиномдық уақытта көптік бірегей түрлендіріле алатын болса. Бұл, әрбір co NP проблемасы L үшін, L-дің кез келген мысалын C-нің сол шындық мәнімен сәйкес мысалына түрлендіретін полиномдық уақыт алгоритмі бар дегенді білдіреді. Салдарынан, егер C үшін полиномдық уақыт алгоритмі болса, онда барлық co NP проблемаларын полиномдық уақытта шеше аламыз.
A decision problem C is co NP complete if it is in co NP and if every problem in co NP is polynomial time many one reducible to it. This means that for every co NP problem L, there exists a polynomial time algorithm which can transform any instance of L into an instance of C with the same truth value. As a consequence, if we had a polynomial time algorithm for C, we could solve all co NP problems in polynomial time.
Мысал
Co NP толық проблемасының бір мысалы – таутология, берілген Буль формуласының таутология екенін анықтау мәселесі; яғни, айнымалыларға нақты/жалған мәндердің кез келген мүмкін комбинациясы тура нәтиже береді. Бұл Бульдік қанағаттандырылу мәселесімен тығыз байланысты, ол мұндай комбинацияның кем дегенде біреуі бар ма деп сұрайды және NP толық.
One example of a co NP complete problem is tautology, the problem of determining whether a given Boolean formula is a tautology; that is, whether every possible assignment of true/false values to variables yields a true statement. This is closely related to the Boolean satisfiability problem, which asks whether there exists at least one such assignment, and is NP complete.