翻訳と辞書 Words near each other ・ Co-Extra ・ Co-fermentation ・ Co-fired ceramic ・ Co-Freemasonry ・ Co-institutional ・ Co-insurance ・ Co-location (satellite) ・ Co-managed Security ・ Co-marketing ・ Co-ment ・ CO-methylating acetyl-CoA synthase ・ Co-modality ・ Co-Motion Cycles ・ Co-no-Mi-chi ・ Co-NP ・ Co-NP-complete ・ Co-occurrence ・ Co-occurrence matrix ・ Co-occurrence networks ・ Co-Op (podcast) ・ Co-op Atlantic ・ Co-op Block ・ Co-Op Block and J. N. Ireland Bank ・ Co-op Brewery ・ Co-op City Department of Public Safety ・ Co-op City, Bronx ・ CO-OP Financial Services ・ Co-op High School ・ Co-op Insurance Society Ltd v Argyll Stores Holdings Ltd ・ Co-op Kobe Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Co-NP-complete ： ウィキペディア英語版 Co-NP-complete 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 ,〔S. Fortune. A note on sparse complete sets. ''SIAM Journal on Computing'', volume 8, issue 3, pp.431–433. 1979.〕 a critical foundation for Mahaney's theorem. ==Formal definition== 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. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Co-NP-complete」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.