. "Klasa Co-NP \u2013 klasa z\u0142o\u017Cono\u015Bci dope\u0142niaj\u0105ca dla problem\u00F3w decyzyjnych NP. Przyk\u0142adowo dope\u0142nieniem problemu typu \u201Eczy wszystkie elementy zbioru X spe\u0142niaj\u0105 warunek Y\u201D jest \u201Eczy istnieje element zbioru X niespe\u0142niaj\u0105cy warunku Y\u201D. Nie wiadomo czy dope\u0142nienie ka\u017Cdego problemu NP jest NP. Wydaje si\u0119 bowiem, \u017Ce czasem \u0142atwiej pokazywa\u0107 kontrprzyk\u0142ady (weryfikowa\u0107 negatywnie) ni\u017C udowodni\u0107 prawdziwo\u015B\u0107 jakiego\u015B twierdzenia (weryfikowa\u0107 pozytywnie). Wykazano, \u017Ce je\u017Celi NP \u2260 Co-NP, to P \u2260 NP. Jednak implikacja w drug\u0105 stron\u0119 nie zosta\u0142a udowodniona."@pl . . . . . "1069392707"^^ . "Co-NP"@fr . "In der Komplexit\u00E4tstheorie bezeichnet Co-NP eine Komplexit\u00E4tsklasse. In ihr sind genau die Sprachen enthalten, deren Komplement in der Klasse NP liegt. Die Klasse Co-NP besteht demnach aus den Sprachen, f\u00FCr die ein Beweis, dass ein Wort nicht zur Sprache geh\u00F6rt, in Polynomialzeit durch eine nichtdeterministische Turingmaschine \u00FCberpr\u00FCft werden kann."@de . . . . "In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely if only no-instances have a polynomial-length \"certificate\" and there is a polynomial-time algorithm that can be used to verify any purported certificate."@en . "\u0641\u064A \u0639\u0644\u0645 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u064A co-NP \u0647\u064A \u0627\u0644\u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0644\u0645\u064F\u0643\u0645\u0644\u0629 \u0644-NP \u0623\u064A: co-NP={0,1}* \\ NP ."@ar . . "Co-NP"@ko . . . "Co-NP"@ja . . . . . "\u0412 \u0442\u0435\u043E\u0440\u0456\u0457 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456 \u043E\u0431\u0447\u0438\u0441\u043B\u0435\u043D\u044C, co-NP \u2014 \u043A\u043B\u0430\u0441 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456. \u0417\u0430\u0434\u0430\u0447\u0430 \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u043A\u043B\u0430\u0441\u0443 co-NP \u0442\u043E\u0434\u0456 \u0456 \u0442\u0456\u043B\u044C\u043A\u0438 \u0442\u043E\u0434\u0456, \u043A\u043E\u043B\u0438 \u043A\u043E\u043C\u043F\u043B\u0430\u043D\u0430\u0440\u043D\u0430 \u0434\u043E \u043D\u0435\u0457 \u0437\u0430\u0434\u0430\u0447\u0430 \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u043A\u043B\u0430\u0441\u0443 NP. \u041D\u0435\u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u043E, co-NP \u2014 \u043A\u043B\u0430\u0441 \u0437\u0430\u0434\u0430\u0447, \u0434\u043B\u044F \u044F\u043A\u0438\u0445 \u0456\u0441\u043D\u0443\u044E\u0442\u044C \u0435\u0444\u0435\u043A\u0442\u0438\u0432\u043D\u0456 (\u043F\u043E\u043B\u0456\u043D\u043E\u043C\u0456\u0430\u043B\u044C\u043D\u043E\u0457 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456) \u043F\u0435\u0440\u0435\u0432\u0456\u0440\u044E\u0432\u0430\u0447\u0456 \u0434\u043B\u044F \u0432\u0456\u0434\u043F\u043E\u0432\u0456\u0434\u0456 \u00AB\u041D\u0456\u00BB."@uk . "\u5728\u8A08\u7B97\u8907\u96DC\u5EA6\u7406\u8AD6\u4E0A\uFF0C\u53CDNP\u985E\u662F\u8907\u96DC\u5EA6\u985E\u7684\u5176\u4E2D\u4E00\u985E\u3002"@zh . . "En informatique th\u00E9orique, co-NP (ou coNP) est une classe de complexit\u00E9, c'est-\u00E0-dire un ensemble de probl\u00E8mes de d\u00E9cision au sens de la th\u00E9orie de la complexit\u00E9. C'est la classe compl\u00E9mentaire (au sens de la complexit\u00E9) de la classe NP."@fr . "\u0412 \u0442\u0435\u043E\u0440\u0456\u0457 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456 \u043E\u0431\u0447\u0438\u0441\u043B\u0435\u043D\u044C, co-NP \u2014 \u043A\u043B\u0430\u0441 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456. \u0417\u0430\u0434\u0430\u0447\u0430 \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u043A\u043B\u0430\u0441\u0443 co-NP \u0442\u043E\u0434\u0456 \u0456 \u0442\u0456\u043B\u044C\u043A\u0438 \u0442\u043E\u0434\u0456, \u043A\u043E\u043B\u0438 \u043A\u043E\u043C\u043F\u043B\u0430\u043D\u0430\u0440\u043D\u0430 \u0434\u043E \u043D\u0435\u0457 \u0437\u0430\u0434\u0430\u0447\u0430 \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u043A\u043B\u0430\u0441\u0443 NP. \u041D\u0435\u0444\u043E\u0440\u043C\u0430\u043B\u044C\u043D\u043E, co-NP \u2014 \u043A\u043B\u0430\u0441 \u0437\u0430\u0434\u0430\u0447, \u0434\u043B\u044F \u044F\u043A\u0438\u0445 \u0456\u0441\u043D\u0443\u044E\u0442\u044C \u0435\u0444\u0435\u043A\u0442\u0438\u0432\u043D\u0456 (\u043F\u043E\u043B\u0456\u043D\u043E\u043C\u0456\u0430\u043B\u044C\u043D\u043E\u0457 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456) \u043F\u0435\u0440\u0435\u0432\u0456\u0440\u044E\u0432\u0430\u0447\u0456 \u0434\u043B\u044F \u0432\u0456\u0434\u043F\u043E\u0432\u0456\u0434\u0456 \u00AB\u041D\u0456\u00BB. \u0412\u0456\u0437\u044C\u043C\u0435\u043C\u043E \u043F\u0440\u0438\u043A\u043B\u0430\u0434 NP-\u043F\u043E\u0432\u043D\u043E\u0457 \u0437\u0430\u0434\u0430\u0447\u0456 \u043F\u0440\u043E \u0441\u0443\u043C\u0443 \u043F\u0456\u0434\u043C\u043D\u043E\u0436\u0438\u043D: \u00AB\u0414\u0430\u043D\u0430 \u0441\u043A\u0456\u043D\u0447\u0435\u043D\u043D\u0430 \u043C\u043D\u043E\u0436\u0438\u043D\u0430 \u0446\u0456\u043B\u0438\u0445 \u0447\u0438\u0441\u0435\u043B. \u0427\u0438 \u0454 \u0443 \u043D\u0435\u0457 \u0445\u043E\u0447 \u043E\u0434\u043D\u0430 \u043D\u0435\u043F\u043E\u0440\u043E\u0436\u043D\u044F \u043F\u0456\u0434\u043C\u043D\u043E\u0436\u0438\u043D\u0430, \u0441\u0443\u043C\u0430 \u0435\u043B\u0435\u043C\u0435\u043D\u0442\u0456\u0432 \u044F\u043A\u043E\u0457 \u0440\u0456\u0432\u043D\u0430 \u043D\u0443\u043B\u044E?\u00BB \u041A\u043E\u043C\u043B\u0430\u043D\u0430\u0440\u043D\u043E\u044E \u0434\u043E \u0446\u0456\u0454\u0457 \u0437\u0430\u0434\u0430\u0447\u0456 \u0431\u0443\u0434\u0435 \u0442\u0430\u043A\u0430: \u00AB\u0414\u0430\u043D\u0430 \u0441\u043A\u0456\u043D\u0447\u0435\u043D\u043D\u0430 \u043C\u043D\u043E\u0436\u0438\u043D\u0430 \u0446\u0456\u043B\u0438\u0445 \u0447\u0438\u0441\u0435\u043B. \u0427\u0438 \u043A\u043E\u0436\u043D\u0430 \u043D\u0435\u043F\u043E\u0440\u043E\u0436\u043D\u044F \u043C\u0430\u0454 \u043D\u0435\u043D\u0443\u043B\u044C\u043E\u0432\u0443 \u0441\u0443\u043C\u0443 \u0435\u043B\u0435\u043C\u0435\u043D\u0442\u0456\u0432?\u00BB \u0429\u043E\u0431 \u0434\u043E\u0432\u0435\u0441\u0442\u0438 \u0432\u0456\u0434\u043F\u043E\u0432\u0456\u0434\u044C \u00AB\u041D\u0456\u00BB, \u043C\u0430\u0454\u043C\u043E \u043D\u0430\u0434\u0430\u0442\u0438 \u044F\u043A\u0443\u0441\u044C \u043D\u0435\u043F\u043E\u0440\u043E\u0436\u043D\u044E \u043F\u0456\u0434\u043C\u043D\u043E\u0436\u0438\u043D\u0443, \u0441\u0443\u043C\u0430 \u0435\u043B\u0435\u043C\u0435\u043D\u0442\u0456\u0432 \u044F\u043A\u043E\u0457 \u0440\u0456\u0432\u043D\u0430 \u043D\u0443\u043B\u044E. \u0422\u0430\u043A\u0435 \u0434\u043E\u0432\u0435\u0434\u0435\u043D\u043D\u044F \u043B\u0435\u0433\u043A\u043E \u043F\u0435\u0440\u0435\u0432\u0456\u0440\u0438\u0442\u0438 \u0437\u0430 \u043F\u043E\u043B\u0456\u043D\u043E\u043C\u0456\u0430\u043B\u044C\u043D\u0438\u0439 \u0447\u0430\u0441. P, \u043A\u043B\u0430\u0441 \u0437\u0430\u0434\u0430\u0447, \u0440\u043E\u0437\u0432'\u044F\u0437\u043D\u0438\u0445 \u0437\u0430 \u043F\u043E\u043B\u0456\u043D\u043E\u043C\u0456\u0430\u043B\u044C\u043D\u0438\u0439 \u0447\u0430\u0441, \u0454 \u043F\u0456\u0434\u043C\u043D\u043E\u0436\u0438\u043D\u043E\u044E \u044F\u043A NP, \u0442\u0430\u043A \u0456 co-NP.NP \u0456 co-NP \u0432\u0432\u0430\u0436\u0430\u044E\u0442\u044C\u0441\u044F (\u0445\u043E\u0447 \u0446\u0435 \u043D\u0435 \u0434\u043E\u0432\u0435\u0434\u0435\u043D\u043E) \u043D\u0435\u0440\u0456\u0432\u043D\u0438\u043C\u0438. \u042F\u043A\u0449\u043E \u0434\u043B\u044F \u044F\u043A\u043E\u0457-\u043D\u0435\u0431\u0443\u0434\u044C NP-\u043F\u043E\u0432\u043D\u043E\u0457 \u0437\u0430\u0434\u0430\u0447\u0456 \u0434\u043E\u0432\u0435\u0441\u0442\u0438, \u0449\u043E \u0432\u043E\u043D\u0430 \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u043A\u043B\u0430\u0441\u0443 co-NP, \u0442\u043E \u0446\u0435 \u043E\u0437\u043D\u0430\u0447\u0430\u043B\u043E \u0431 \u0440\u0456\u0432\u043D\u0456\u0441\u0442\u044C \u0446\u0438\u0445 \u043A\u043B\u0430\u0441\u0456\u0432. \u041E\u0441\u043A\u0456\u043B\u044C\u043A\u0438 \u0431\u0443\u0434\u044C-\u044F\u043A\u0430 NP-\u0437\u0430\u0434\u0430\u0447\u0430 (\u0437\u0430 \u043E\u0437\u043D\u0430\u0447\u0435\u043D\u043D\u044F\u043C) \u0437\u0432\u043E\u0434\u0438\u0442\u044C\u0441\u044F \u0434\u043E NP-\u043F\u043E\u0432\u043D\u043E\u0457 \u0437\u0430 \u043F\u043E\u043B\u0456\u043D\u043E\u043C\u0456\u0430\u043B\u044C\u043D\u0438\u0439 \u0447\u0430\u0441.\u0417\u0430\u0434\u0430\u0447\u0430, \u0449\u043E \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u044F\u043A \u0434\u043E NP, \u0442\u0430\u043A \u0456 \u0434\u043E co-NP, \u0434\u043E\u0441\u0438\u0442\u044C \u0439\u043C\u043E\u0432\u0456\u0440\u043D\u043E(\u0437\u0430 \u043F\u0440\u0438\u043F\u0443\u0449\u0435\u043D\u043D\u044F\u043C \u043F\u0440\u043E \u043D\u0435\u0440\u0456\u0432\u043D\u0456\u0441\u0442\u044C \u0446\u0438\u0445 \u043A\u043B\u0430\u0441\u0456\u0432) \u043D\u0435 \u0454 NP-\u043F\u043E\u0432\u043D\u043E\u044E. \u041F\u0440\u0438\u043A\u043B\u0430\u0434\u043E\u043C \u0437\u0430\u0434\u0430\u0447\u0456, \u0449\u043E \u043D\u0430\u043B\u0435\u0436\u0438\u0442\u044C \u044F\u043A \u0434\u043E NP, \u0442\u0430\u043A \u0456 \u0434\u043E co-NP, \u0454 \u0444\u0430\u043A\u0442\u043E\u0440\u0438\u0437\u0430\u0446\u0456\u044F \u0447\u0438\u0441\u043B\u0430: \"\u0434\u0430\u043D\u043E \u043D\u0430\u0442\u0443\u0440\u0430\u043B\u044C\u043D\u0456 \u0447\u0438\u0441\u043B\u0430 m \u0442\u0430 n. \u0412\u0438\u0437\u043D\u0430\u0447\u0438\u0442\u0438, \u0447\u0438 m \u043C\u0430\u0454 \u043F\u0440\u043E\u0441\u0442\u0438\u0439 \u0434\u0456\u043B\u044C\u043D\u0438\u043A, \u043C\u0435\u043D\u0448\u0438\u0439 \u0437\u0430 n. \u041D\u0430\u043B\u0435\u0436\u043D\u0456\u0441\u0442\u044C \u0434\u043E NP \u043E\u0447\u0435\u0432\u0438\u0434\u043D\u0430: \u044F\u043A\u0449\u043E m \u043C\u0430\u0454 \u0442\u0430\u043A\u0438\u0439 \u0434\u0456\u043B\u044C\u043D\u0438\u043A, \u0442\u043E \u0432\u0456\u043D \u0456 \u0454 \u043F\u0456\u0434\u0442\u0432\u0435\u0440\u0434\u0436\u0435\u043D\u043D\u044F\u043C \u0432\u0456\u0434\u043F\u043E\u0432\u0456\u0434\u0456. \u0414\u043E\u0432\u0435\u0434\u0435\u043D\u043D\u044F \u043D\u0430\u043B\u0435\u0436\u043D\u043E\u0441\u0442\u0456 \u0434\u043E co-NP \u0441\u043A\u043B\u0430\u0434\u043D\u0456\u0448\u0435: \u0434\u043B\u044F \u043F\u0435\u0440\u0435\u0432\u0456\u0440\u043A\u0438 \u0432\u0456\u0434\u043F\u043E\u0432\u0456\u0434\u0456 \u043C\u0430\u0454\u043C\u043E \u043F\u0435\u0440\u0435\u043B\u0456\u0447\u0438\u0442\u0438 \u043F\u0440\u043E\u0441\u0442\u0456 \u0434\u0456\u043B\u044C\u043D\u0438\u043A\u0438 m \u0442\u0430 \u0434\u043E\u0432\u0435\u0441\u0442\u0438 \u0434\u043B\u044F \u043A\u043E\u0436\u043D\u043E\u0433\u043E, \u0449\u043E \u0432\u0456\u043D \u0454 \u043F\u0440\u043E\u0441\u0442\u0438\u043C. \u0406\u043D\u0448\u0430 \u0437\u0430\u0434\u0430\u0447\u0430 \u0437 \u043F\u0435\u0440\u0435\u0442\u0438\u043D\u0443 NP \u2229 co-NP \u2014 \u043F\u0435\u0440\u0435\u0432\u0456\u0440\u043A\u0430 \u0447\u0438 \u0454 \u0447\u0438\u0441\u043B\u043E \u043F\u0440\u043E\u0441\u0442\u0438\u043C."@uk . "Klasa Co-NP \u2013 klasa z\u0142o\u017Cono\u015Bci dope\u0142niaj\u0105ca dla problem\u00F3w decyzyjnych NP. Przyk\u0142adowo dope\u0142nieniem problemu typu \u201Eczy wszystkie elementy zbioru X spe\u0142niaj\u0105 warunek Y\u201D jest \u201Eczy istnieje element zbioru X niespe\u0142niaj\u0105cy warunku Y\u201D. Nie wiadomo czy dope\u0142nienie ka\u017Cdego problemu NP jest NP. Wydaje si\u0119 bowiem, \u017Ce czasem \u0142atwiej pokazywa\u0107 kontrprzyk\u0142ady (weryfikowa\u0107 negatywnie) ni\u017C udowodni\u0107 prawdziwo\u015B\u0107 jakiego\u015B twierdzenia (weryfikowa\u0107 pozytywnie). Wykazano, \u017Ce je\u017Celi NP \u2260 Co-NP, to P \u2260 NP. Jednak implikacja w drug\u0105 stron\u0119 nie zosta\u0142a udowodniona."@pl . . "Na Teoria da complexidade, co-NP \u00E9 uma Classe de complexidade. Um problema \u00E9 membro de co-NP se e somente se seu complemento esta na classe de complexidade NP. Em outras palavras, co-NP \u00E9 a classe de problemas para qual existe a prova, de forma eficiente, para n\u00E3o exist\u00EAncia de inst\u00E2ncia, os chamados contra-exemplos. Se um problema pode ser apresentado com sendo tanto em NP quanto em co-NP, isso serve de evid\u00EAncia de que esse problema provavelmente n\u00E3o \u00E9 NP-completo,caso contr\u00E1rio NP = co-NP."@pt . . . . . "co-NP\u3068\u306F\u8A08\u7B97\u91CF\u7406\u8AD6\u306B\u304A\u3051\u308B\u554F\u984C\u30AF\u30E9\u30B9\u306E\u4E00\u3064\u3067\u3042\u308B\u3002"@ja . "\u0641\u064A \u0639\u0644\u0645 \u0627\u0644\u062A\u0639\u0642\u064A\u062F \u0627\u0644\u062D\u0633\u0627\u0628\u064A co-NP \u0647\u064A \u0627\u0644\u0645\u062C\u0645\u0648\u0639\u0629 \u0627\u0644\u0645\u064F\u0643\u0645\u0644\u0629 \u0644-NP \u0623\u064A: co-NP={0,1}* \\ NP ."@ar . "Nella teoria della complessit\u00E0 computazionale, \u00E8 la classe di problemi complementari a quelli della classe . In maniera pi\u00F9 formale si ha che se \u00E8 un problema su un alfabeto allora esso \u00E8 un problema della classe se e solo se \u00E8 un problema di classe . Per quanto riguarda l'uguaglianza non ci si pu\u00F2 esprimere. Ecco perch\u00E9 non si pu\u00F2 dire nulla a proposito dell'uguaglianza ed ."@it . . . . "En teor\u00EDa de la complejidad computacional, la clase de complejidad co-NP es el conjunto de los problemas de decisi\u00F3n complementarios a los de la clase NP. Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa est\u00E1n invertidas. La clase de complejidad P es un subconjunto tanto de NP como de co-NP y se piensa que la inclusi\u00F3n es estricta en ambos casos. Se piensa tambi\u00E9n que NP y co-NP son diferentes. De ser cierto esto, ning\u00FAn problema de NP-completo podr\u00EDa estar en co-NP y ning\u00FAn problema de co-NP-completo podr\u00EDa estar en NP. Esto se demuestra como sigue: Si hubiera un problema en NP-completo y en co-NP al mismo tiempo, todo problema de NP se reducir\u00EDa en \u00E9l, se deduce que para todo problema en NP se podr\u00EDa construir una m\u00E1quina de Turing no determinista que decidiera el problema complementario en tiempo polin\u00F3mico, es decir, NP ser\u00EDa un subconjunto de co-NP y, por tanto los complementos de NP ser\u00EDan subconjunto de los complementos de co-NP, es decir, co-NP ser\u00EDa un subconjunto de NP, Por tanto NP y co-NP ser\u00EDan el mismo conjunto. De forma sim\u00E9trica se demuestra que ning\u00FAn problema en co-NP-completo puede estar en NP. \n* Datos: Q955748"@es . . . . . . . "Co-NP"@pt . . . . . "June 2021"@en . . "Nella teoria della complessit\u00E0 computazionale, \u00E8 la classe di problemi complementari a quelli della classe . In maniera pi\u00F9 formale si ha che se \u00E8 un problema su un alfabeto allora esso \u00E8 un problema della classe se e solo se \u00E8 un problema di classe . Per quanto riguarda l'uguaglianza non ci si pu\u00F2 esprimere. Infatti per vedere se un certo input sia tale da essere di o di non esserlo si dovrebbe attendere che tutte le possibili computazioni della macchina di Turing non deterministica che accetta facciano il loro corso; ossia per avere la certezza che nessuna computazione si dovrebbe arrestare mentre se allora almeno una di tali computazioni si dovrebbe arrestare.Per far ci\u00F2 non si impiega per\u00F2 un tempo polinomiale. Ecco perch\u00E9 non si pu\u00F2 dire nulla a proposito dell'uguaglianza ed ."@it . . "Co-NP"@it . "En complexitat computacional, co-NP \u00E9s la classe de complexitat que cont\u00E9 els problemes de decisi\u00F3 complementaris de la classe NP. Per problema complementari s'ent\u00E9n aquell que te les respostes invertides. Tamb\u00E9 es pot dir que els la classe co-NP \u00E9s el conjunt de problemes de decisi\u00F3 que una m\u00E0quina de Turing no determinista respon \u00ABno\u00BB (o rebutja) en un temps polin\u00F2mic."@ca . . "Co-NP"@de . . . "Co-NP (Complexitat)"@ca . "\uACC4\uC0B0 \uBCF5\uC7A1\uB3C4 \uC774\uB860\uC5D0\uC11C co-NP\uB294 \uBCF5\uC7A1\uB3C4 \uC885\uB958\uC774\uB2E4. \uBB38\uC81C \uAC00 co-NP\uC5D0 \uB4E4\uC5B4 \uC788\uB2E4\uB294 \uAC83\uC740 \uADF8 \uBB38\uC81C\uC778 \uAC00 NP\uC5D0 \uC18D\uD55C\uB2E4\uB294 \uAC83\uACFC \uB3D9\uCE58\uC774\uB2E4. \uAC04\uB2E8\uD788 \uB9D0\uD558\uBA74, co-NP\uB294 \uC544\uB2C8\uC624 \uBCF4\uAE30(\uBC18\uB840\uB77C\uACE0\uB3C4 \uD55C\uB2E4)\uC5D0 \uB300\uD574 \uD6A8\uC728\uC801\uC73C\uB85C \uAC80\uC99D\uD560 \uC218 \uC788\uB294 \uC99D\uBA85\uC774 \uC788\uB294 \uBB38\uC81C\uC758 \uC9D1\uD569\uC774\uB2E4. NP-\uC644\uC804 \uBB38\uC81C \uC911 \uBD80\uBD84\uC9D1\uD569 \uD569 \uBB38\uC81C\uAC00 \uC788\uB2E4. \uC774 \uBB38\uC81C\uB294 \uC815\uC218 \uC720\uD55C\uC9D1\uD569\uC774 \uC788\uC744 \uB54C, \uC774 \uC9D1\uD569\uC758 \uACF5\uC9D1\uD569\uC774 \uC544\uB2CC \uBD80\uBD84\uC9D1\uD569 \uC911 \uC6D0\uC18C\uB97C \uB2E4 \uB354\uD558\uBA74 0\uC774 \uB418\uB294 \uAC83\uC774 \uC788\uB294\uC9C0\uB97C \uBB3B\uB294 \uBB38\uC81C\uC774\uB2E4. \uC774 \uBB38\uC81C\uC758 \uBCF4\uC644 \uBB38\uC81C\uB294 co-NP\uC5D0 \uB4E4\uC5B4\uAC00\uB294\uB370, \uC815\uC218 \uC720\uD55C\uC9D1\uD569\uC774 \uC8FC\uC5B4\uC9C8 \uB54C, \uACF5\uC9D1\uD569\uC774 \uC544\uB2CC \uBD80\uBD84\uC9D1\uD569\uC740 \uBAA8\uB450, \uC6D0\uC18C\uB97C \uB2E4 \uB354\uD588\uC744 \uB54C 0\uC774 \uC544\uB2CC\uC9C0\uB97C \uBB3B\uB294 \uBB38\uC81C\uAC00 \uB41C\uB2E4. \"\uC544\uB2C8\uC624\" \uBCF4\uAE30\uC5D0 \uB300\uD55C \uC99D\uBA85\uC744 \uD558\uB824\uBA74, \uD569\uC774 0\uC774 \uB418\uACE0 \uACF5\uC9D1\uD569\uC774 \uC544\uB2CC \uBD80\uBD84\uC9D1\uD569\uC744 \uCC3E\uC544\uC57C \uD55C\uB2E4. \uADF8\uB807\uAC8C \uD558\uBA74 \uC774 \uC99D\uBA85\uC740 \uAC80\uC99D\uD558\uAE30 \uC26C\uC6CC\uC9C4\uB2E4. \uB2E4\uD56D \uC2DC\uAC04\uC5D0 \uD480 \uC218 \uC788\uB294 \uBB38\uC81C\uC778 P\uB294 NP\uC640 co-NP \uBAA8\uB450\uC758 \uBD80\uBD84\uC9D1\uD569\uC774\uB2E4. P\uB294 \uB450 \uACBD\uC6B0 \uBAA8\uB450 \uC9C4\uBD80\uBD84\uC9D1\uD569\uC77C \uAC83\uC73C\uB85C \uCD94\uCE21\uD558\uACE0 \uC788\uB2E4. (\uD55C\uCABD\uB9CC \uC9C4\uBD80\uBD84\uC9D1\uD569\uC774\uACE0, \uB2E4\uB978 \uCABD\uC740 \uC544\uB2CC \uACBD\uC6B0\uB294 \uBD88\uAC00\uB2A5\uD568\uC744 \uBCF4\uC77C \uC218 \uC788\uB2E4.) NP\uC640 co-NP \uC5ED\uC2DC, \uAC19\uC740 \uC9D1\uD569\uC774 \uC544\uB2D0 \uAC83\uC774\uB2E4. \uB9CC\uC57D \uADF8\uB807\uC9C0 \uC54A\uB2E4\uBA74, NP-\uC644\uC804 \uBB38\uC81C\uAC00 co-NP\uC5D0 \uB4E4\uC5B4\uAC08 \uC218 \uC788\uACE0, co-NP-\uC644\uC804 \uBB38\uC81C\uAC00 NP\uC5D0 \uB4E4\uC5B4\uAC08 \uC218 \uC788\uAE30 \uB54C\uBB38\uC774\uB2E4. \uC774\uB294 \uB2E4\uC74C\uACFC \uAC19\uC774 \uBCF4\uC77C \uC218 \uC788\uB2E4. co-NP\uC5D0 \uB4E4\uC5B4\uAC00\uB294 NP-\uC644\uC804 \uBB38\uC81C\uAC00 \uC788\uB2E4\uACE0 \uD558\uC790. \uBAA8\uB4E0 NP \uBB38\uC81C\uB294 \uC774 \uBB38\uC81C\uB85C \uD658\uC0B0\uD560 \uC218 \uC788\uAE30 \uB54C\uBB38\uC5D0, \uAC01 NP\uBB38\uC81C\uC5D0 \uB300\uD574\uC11C \uADF8 \uBCF4\uC644 \uBB38\uC81C\uB97C \uB2E4\uD56D \uC2DC\uAC04\uC5D0 \uD310\uC815\uD560 \uC218 \uC788\uB294 \uBE44\uACB0\uC815\uC801\uC778 \uD29C\uB9C1 \uAE30\uACC4\uB97C \uB9CC\uB4E4 \uC218 \uC788\uB2E4. \uB2E4\uC2DC \uB9D0\uD574\uC11C, NP\uAC00 co-NP\uC758 \uBD80\uBD84\uC9D1\uD569\uC774 \uB41C\uB2E4. \uB530\uB77C\uC11C NP \uBB38\uC81C\uC758 \uBCF4\uC644\uC744 \uBAA8\uC740 \uC9D1\uD569\uC774 co-NP \uBB38\uC81C\uC758 \uBCF4\uC644\uC744 \uBAA8\uC740 \uC9D1\uD569\uC758 \uBD80\uBD84\uC9D1\uD569\uC774 \uB41C\uB2E4. \uACE7, co-NP\uAC00 NP\uC758 \uBD80\uBD84\uC9D1\uD569\uC774 \uB41C\uB2E4. \uC55E\uC5D0\uC11C NP\uAC00 co-NP\uC758 \uBD80\uBD84\uC9D1\uD569\uC784\uC744 \uBCF4\uC600\uC73C\uBBC0\uB85C, \uC774\uB294 \uB450 \uC9D1\uD569\uC774 \uAC19\uB2E4\uB294 \uB73B\uC774 \uB41C\uB2E4. co-NP-\uC644\uC804 \uBB38\uC81C\uAC00 NP\uC77C \uC218 \uC5C6\uC74C\uC744 \uBCF4\uC774\uB294 \uC99D\uBA85\uC740 \uC774 \uC99D\uBA85\uACFC \uB300\uCE6D\uC744 \uC774\uB8EC\uB2E4. \uC5B4\uB5A4 \uBB38\uC81C\uAC00 NP\uC640 co-NP \uB458 \uB2E4 \uB41C\uB2E4\uB294 \uAC83\uC744 \uBCF4\uC600\uB2E4\uBA74, \uC774\uB294 \uADF8 \uBB38\uC81C\uAC00 NP-\uC644\uC804\uC774 \uC544\uB2D0 \uAC83\uC774\uB77C\uB294 \uAC15\uB825\uD55C \uC99D\uAC70\uAC00 \uB41C\uB2E4. (NP-\uC644\uC804\uC774\uB77C\uBA74 NP = co-NP\uC774\uAE30 \uB54C\uBB38) \uC815\uC218\uC758 \uC18C\uC778\uC218 \uBD84\uD574 \uBB38\uC81C\uB294 NP\uC640 co-NP\uC5D0 \uBAA8\uB450 \uB4E4\uC5B4\uAC00\uB294, \uC720\uBA85\uD55C \uBB38\uC81C\uC774\uB2E4. \uC591\uC758 \uC815\uC218 m\uACFC n\uC774 \uC788\uC744 \uB54C m\uC5D0 n\uBCF4\uB2E4 \uC791\uACE0 1\uBCF4\uB2E4 \uD070 \uC57D\uC218\uAC00 \uC788\uB294\uC9C0\uB97C \uBB3B\uB294\uB2E4. \uC788\uB294 \uACBD\uC6B0\uB97C \uBCF4\uC774\uB294 \uCABD\uC740 \uC27D\uB2E4. m\uC5D0 \uADF8\uB7F0 \uC57D\uC218\uAC00 \uC788\uB2E4\uBA74, \uADF8 \uC57D\uC218\uB85C \uB098\uB204\uC5B4 \uBCF4\uBA74 \uB41C\uB2E4. \uBC18\uB300\uCABD\uC740 \uC880 \uC5B4\uB824\uC6B4\uB370, \uADF8\uB7F0 \uC57D\uC218\uAC00 \uC5C6\uB2E4\uB294 \uAC83\uC744 \uBCF4\uC774\uB824\uBA74 \uC77C\uC77C\uC774 \uB098\uB204\uC5B4 \uBCF4\uC544\uC57C \uD55C\uB2E4. \uC18C\uC778\uC218 \uBD84\uD574 \uBB38\uC81C\uB97C \uC18C\uC218 \uBB38\uC81C\uC640 \uD5F7\uAC08\uB9AC\uB294 \uC0AC\uB78C\uC774 \uB9CE\uB2E4. \uC18C\uC218 \uBB38\uC81C\uB3C4 \uC18C\uC778\uC218 \uBD84\uD574 \uBB38\uC81C\uCC98\uB7FC NP\uC640 co-NP \uB458 \uB2E4\uC5D0 \uB4E4\uC5B4\uAC04\uB2E4. \uADF8\uB7EC\uB098 \uC544\uC9C1 \uD655\uC2E4\uCE58 \uC54A\uC740 \uC18C\uC778\uC218 \uBD84\uD574\uC640\uB294 \uB2EC\uB9AC, \uC18C\uC218 \uBB38\uC81C\uB294 P\uC774\uB2E4."@ko . "Co-NP"@en . "Na Teoria da complexidade, co-NP \u00E9 uma Classe de complexidade. Um problema \u00E9 membro de co-NP se e somente se seu complemento esta na classe de complexidade NP. Em outras palavras, co-NP \u00E9 a classe de problemas para qual existe a prova, de forma eficiente, para n\u00E3o exist\u00EAncia de inst\u00E2ncia, os chamados contra-exemplos. Um exemplo de um problema NP-Completo \u00E9 o Problema da soma dos subconjuntos: dado um conjunto finito de n\u00FAmeros inteiros, existe um subconjunto n\u00E3o vazio cuja soma \u00E9 zero? Para dar a prova de que existe uma inst\u00E2ncia, primeiro \u00E9 necess\u00E1rio especificar um subconjunto n\u00E3o vazio que tenha como soma zero. O problema complementar esta em co-NP e pergunta: \"dado um conjunto finito de inteiros, cada um dos subconjuntos n\u00E3o tem soma zero?\". Para provar a n\u00E3o exist\u00EAncia de uma inst\u00E2ncia voc\u00EA precisa especificar um subconjunto n\u00E3o vazio que tenha soma zero, que \u00E9 facilmente verific\u00E1vel.P, a classe dos problemas resolv\u00EDveis em tempo polinomial, \u00E9 um subconjunto de tanto NP quanto co-NP. P \u00E9 considerado estritamente um subconjunto de ambas classes (e comprovadamente n\u00E3o pode ser rigoroso em um caso, e n\u00E3o em outro). NP e co-NP s\u00E3o tamb\u00E9m considerados iguais. Caso seja, ent\u00E3o um problema que n\u00E3o seja NP-completo pode ser NP e um problema que n\u00E3o seja co-NP-completo pode ser NP. Isso pode ser demonstrado como se segue. Assumindo que existe um problema NP-completo que esta em co-NP. J\u00E1 que todos os problemas em NP podem ser reduzidos para esse problemas, ent\u00E3o para todos os problemas em NP nos podemos construir a M\u00E1quina de Turing n\u00E3o determin\u00EDstica que decide o complemento desse problema em tempo polinomial,ou seja, NP \u00E9 um subconjunto de co-NP. Visto que o conjunto de complementos dos problemas NP \u00E9 subconjunto do conjunto de complementos dos problemas em co-NO, ou seja, co-NP \u00E9 um subconjunto de NO.Uma vez que j\u00E1 sabia que NP \u00E9 subconjunto de co-NP, ent\u00E3o eles s\u00E3o iguais. A prova para o fato de que nenhum problema co-NP-completo pode ser em NP \u00E9 sim\u00E9trica. Se um problema pode ser apresentado com sendo tanto em NP quanto em co-NP, isso serve de evid\u00EAncia de que esse problema provavelmente n\u00E3o \u00E9 NP-completo,caso contr\u00E1rio NP = co-NP. Um exemplo de problema que sabe-se estar em NP e em co-NP \u00E9 a Fatora\u00E7\u00E3o de inteiros: dado n\u00FAmeros inteiros positivos m e n determine se m tem um fator menor que n e maior que um. A participa\u00E7\u00E3o em NP \u00E9 clase; se m tem um fator, entao o fator \u00E9 a prova. Participa\u00E7\u00E3o em co-NP \u00E9 mais sutil; primeiro \u00E9 preciso lista os fatores primos de m e fornecer uma certificado de primariedade para cada um. Fatora\u00E7\u00E3o de inteiros \u00E9 muitas vezes confundido com o problema da primariedade. Ambos testes de primariedade e fatora\u00E7\u00E3o s\u00E3o conhecidos como problemas No e Co-NP. O Teste de primalidade AKS, publicado em 2002, prova que o teste de primariedade tamb\u00E9m esta em P, enquanto que fatora\u00E7\u00E3o pode ou n\u00E3o ter um algoritmo em tempo polinomial."@pt . . "how complex is such a certificate?"@en . . . . "5795"^^ . . "co-NP\u3068\u306F\u8A08\u7B97\u91CF\u7406\u8AD6\u306B\u304A\u3051\u308B\u554F\u984C\u30AF\u30E9\u30B9\u306E\u4E00\u3064\u3067\u3042\u308B\u3002"@ja . "\u041A\u043B\u0430\u0441 \u0441\u043A\u043B\u0430\u0434\u043D\u043E\u0441\u0442\u0456 co-NP"@uk . "En informatique th\u00E9orique, co-NP (ou coNP) est une classe de complexit\u00E9, c'est-\u00E0-dire un ensemble de probl\u00E8mes de d\u00E9cision au sens de la th\u00E9orie de la complexit\u00E9. C'est la classe compl\u00E9mentaire (au sens de la complexit\u00E9) de la classe NP."@fr . . "\u53CDNP"@zh . "In der Komplexit\u00E4tstheorie bezeichnet Co-NP eine Komplexit\u00E4tsklasse. In ihr sind genau die Sprachen enthalten, deren Komplement in der Klasse NP liegt. Die Klasse Co-NP besteht demnach aus den Sprachen, f\u00FCr die ein Beweis, dass ein Wort nicht zur Sprache geh\u00F6rt, in Polynomialzeit durch eine nichtdeterministische Turingmaschine \u00FCberpr\u00FCft werden kann."@de . . . . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u0447\u0430\u0441\u0442\u043E \u0440\u0430\u0441\u0441\u043C\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044F \u043A\u043B\u0430\u0441\u0441, \u0442\u0435\u0441\u043D\u043E \u0441\u0432\u044F\u0437\u0430\u043D\u043D\u044B\u0439 \u0441 P \u0438 NP, \u2014 \u043A\u043B\u0430\u0441\u0441 \u0434\u043E\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u0439 \u044F\u0437\u044B\u043A\u043E\u0432 \u0438\u0437 NP, \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u043C\u044B\u0439 co-NP."@ru . . "\u5728\u8A08\u7B97\u8907\u96DC\u5EA6\u7406\u8AD6\u4E0A\uFF0C\u53CDNP\u985E\u662F\u8907\u96DC\u5EA6\u985E\u7684\u5176\u4E2D\u4E00\u985E\u3002"@zh . . . . . . . "\u0643\u0648-\u0625\u0646 \u0628\u064A"@ar . . "Klasa Co-NP"@pl . "En complexitat computacional, co-NP \u00E9s la classe de complexitat que cont\u00E9 els problemes de decisi\u00F3 complementaris de la classe NP. Per problema complementari s'ent\u00E9n aquell que te les respostes invertides. Tamb\u00E9 es pot dir que els la classe co-NP \u00E9s el conjunt de problemes de decisi\u00F3 que una m\u00E0quina de Turing no determinista respon \u00ABno\u00BB (o rebutja) en un temps polin\u00F2mic. La classe de complexitat P \u00E9s un subconjunt tant de NP com de co-NP i es pensa que la inclusi\u00F3 \u00E9s estricta en tots dos casos. Es pensa tamb\u00E9 que NP i co-NP son diferents. Si aix\u00F2 fos cert, cap problema NP-complet podria estar a co-NP i cap problema de co-NP-complet podria estar a NP. Un exemple de problema que se sap que \u00E9s NP i co-NP \u00E9s la factoritzaci\u00F3 d'enters: donat dos nombres positius i enters m i n determinar si m t\u00E9 un factor menor que n i m\u00E9s gran que 1. Que pertany a NP \u00E9s clar: si m te dit factor, llavors el propi factor \u00E9s un certificat. Que pertanyi a la classe co-NP \u00E9s tamb\u00E9 evident: es pot obtenir la llista de factors primers de m, tots m\u00E9s grans o iguals a n, que el verificador pot comprovar si \u00E9s v\u00E0lid per multiplicacions i el . No es coneix cap algorisme per factoritzar en temps polin\u00F2mic, i per tant se sap que aquest problema est\u00E0 a NP i co-NP per\u00F2 no se sap si est\u00E0 tamb\u00E9 a P."@ca . "\uACC4\uC0B0 \uBCF5\uC7A1\uB3C4 \uC774\uB860\uC5D0\uC11C co-NP\uB294 \uBCF5\uC7A1\uB3C4 \uC885\uB958\uC774\uB2E4. \uBB38\uC81C \uAC00 co-NP\uC5D0 \uB4E4\uC5B4 \uC788\uB2E4\uB294 \uAC83\uC740 \uADF8 \uBB38\uC81C\uC778 \uAC00 NP\uC5D0 \uC18D\uD55C\uB2E4\uB294 \uAC83\uACFC \uB3D9\uCE58\uC774\uB2E4. \uAC04\uB2E8\uD788 \uB9D0\uD558\uBA74, co-NP\uB294 \uC544\uB2C8\uC624 \uBCF4\uAE30(\uBC18\uB840\uB77C\uACE0\uB3C4 \uD55C\uB2E4)\uC5D0 \uB300\uD574 \uD6A8\uC728\uC801\uC73C\uB85C \uAC80\uC99D\uD560 \uC218 \uC788\uB294 \uC99D\uBA85\uC774 \uC788\uB294 \uBB38\uC81C\uC758 \uC9D1\uD569\uC774\uB2E4. NP-\uC644\uC804 \uBB38\uC81C \uC911 \uBD80\uBD84\uC9D1\uD569 \uD569 \uBB38\uC81C\uAC00 \uC788\uB2E4. \uC774 \uBB38\uC81C\uB294 \uC815\uC218 \uC720\uD55C\uC9D1\uD569\uC774 \uC788\uC744 \uB54C, \uC774 \uC9D1\uD569\uC758 \uACF5\uC9D1\uD569\uC774 \uC544\uB2CC \uBD80\uBD84\uC9D1\uD569 \uC911 \uC6D0\uC18C\uB97C \uB2E4 \uB354\uD558\uBA74 0\uC774 \uB418\uB294 \uAC83\uC774 \uC788\uB294\uC9C0\uB97C \uBB3B\uB294 \uBB38\uC81C\uC774\uB2E4. \uC774 \uBB38\uC81C\uC758 \uBCF4\uC644 \uBB38\uC81C\uB294 co-NP\uC5D0 \uB4E4\uC5B4\uAC00\uB294\uB370, \uC815\uC218 \uC720\uD55C\uC9D1\uD569\uC774 \uC8FC\uC5B4\uC9C8 \uB54C, \uACF5\uC9D1\uD569\uC774 \uC544\uB2CC \uBD80\uBD84\uC9D1\uD569\uC740 \uBAA8\uB450, \uC6D0\uC18C\uB97C \uB2E4 \uB354\uD588\uC744 \uB54C 0\uC774 \uC544\uB2CC\uC9C0\uB97C \uBB3B\uB294 \uBB38\uC81C\uAC00 \uB41C\uB2E4. \"\uC544\uB2C8\uC624\" \uBCF4\uAE30\uC5D0 \uB300\uD55C \uC99D\uBA85\uC744 \uD558\uB824\uBA74, \uD569\uC774 0\uC774 \uB418\uACE0 \uACF5\uC9D1\uD569\uC774 \uC544\uB2CC \uBD80\uBD84\uC9D1\uD569\uC744 \uCC3E\uC544\uC57C \uD55C\uB2E4. \uADF8\uB807\uAC8C \uD558\uBA74 \uC774 \uC99D\uBA85\uC740 \uAC80\uC99D\uD558\uAE30 \uC26C\uC6CC\uC9C4\uB2E4. \uC5B4\uB5A4 \uBB38\uC81C\uAC00 NP\uC640 co-NP \uB458 \uB2E4 \uB41C\uB2E4\uB294 \uAC83\uC744 \uBCF4\uC600\uB2E4\uBA74, \uC774\uB294 \uADF8 \uBB38\uC81C\uAC00 NP-\uC644\uC804\uC774 \uC544\uB2D0 \uAC83\uC774\uB77C\uB294 \uAC15\uB825\uD55C \uC99D\uAC70\uAC00 \uB41C\uB2E4. (NP-\uC644\uC804\uC774\uB77C\uBA74 NP = co-NP\uC774\uAE30 \uB54C\uBB38)"@ko . "examples of duals for decision/optimization problems in NP and co-NP"@en . . . "6184"^^ . . "\u041A\u043B\u0430\u0441\u0441 co-NP"@ru . . . "In computational complexity theory, co-NP is a complexity class. A decision problem X is a member of co-NP if and only if its complement X is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely if only no-instances have a polynomial-length \"certificate\" and there is a polynomial-time algorithm that can be used to verify any purported certificate. That is, co-NP is the set of decision problems where there exists a polynomial p(n) and a polynomial-time bounded Turing machine M such that for every instance x, x is a no-instance if and only if: for some possible certificate c of length bounded by p(n), the Turing machine M accepts the pair (x, c)."@en . "\u0412 \u0442\u0435\u043E\u0440\u0438\u0438 \u0430\u043B\u0433\u043E\u0440\u0438\u0442\u043C\u043E\u0432 \u0447\u0430\u0441\u0442\u043E \u0440\u0430\u0441\u0441\u043C\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044F \u043A\u043B\u0430\u0441\u0441, \u0442\u0435\u0441\u043D\u043E \u0441\u0432\u044F\u0437\u0430\u043D\u043D\u044B\u0439 \u0441 P \u0438 NP, \u2014 \u043A\u043B\u0430\u0441\u0441 \u0434\u043E\u043F\u043E\u043B\u043D\u0435\u043D\u0438\u0439 \u044F\u0437\u044B\u043A\u043E\u0432 \u0438\u0437 NP, \u043D\u0430\u0437\u044B\u0432\u0430\u0435\u043C\u044B\u0439 co-NP."@ru . . . . . "Co-NP"@es . . "En teor\u00EDa de la complejidad computacional, la clase de complejidad co-NP es el conjunto de los problemas de decisi\u00F3n complementarios a los de la clase NP. Por problema complementario se entiende aquel que cuyas respuestas positiva o negativa est\u00E1n invertidas. La clase de complejidad P es un subconjunto tanto de NP como de co-NP y se piensa que la inclusi\u00F3n es estricta en ambos casos. Se piensa tambi\u00E9n que NP y co-NP son diferentes. De ser cierto esto, ning\u00FAn problema de NP-completo podr\u00EDa estar en co-NP y ning\u00FAn problema de co-NP-completo podr\u00EDa estar en NP. \n* Datos: Q955748"@es .