co-NPとは計算複雑性理論における複雑性クラスの一つ Complement of NP の略である。
co-NP は次の定義で表される問題のクラスである、「ある決定問題 S の補問題 がクラス NP に属する場合、 S はクラス co-NP に属する」という。ここでいう補問題とは決定問題の yes と no が逆になった問題である。例えば「ある数 N は素数か?」という問題の補問題は「ある数 N は合成数か?」ということになる。P ⊆ NP 同様 P ⊆ co-NP であることが解っている。
もし P=NP であると仮定した場合は NP=co-NP になるということが証明されている。ここから対偶を取ると NP≠co-NP なら P≠NP になると証明できる。このため NP≠co-NP を解く事はP≠NP予想に対する有力な解決手段の一つと初期の頃は考えられていた。しかしながら、この問題は現在においても未解決であり、おそらく P≠NP を解くことと同様かそれ以上に難しいと思われている。
aa
- ab
- af
- ak
- als
- am
- an
- ang
- ar
- arc
- as
- ast
- av
- ay
- az
- ba
- bar
- bat_smg
- bcl
- be
- be_x_old
- bg
- bh
- bi
- bm
- bn
- bo
- bpy
- br
- bs
- bug
- bxr
- ca
- cbk_zam
- cdo
- ce
- ceb
- ch
- cho
- chr
- chy
- co
- cr
- crh
- cs
- csb
- cu
- cv
- cy
- da
- de
- diq
- dsb
- dv
- dz
- ee
- el
- eml
- en
- eo
- es
- et
- eu
- ext
- fa
- ff
- fi
- fiu_vro
- fj
- fo
- fr
- frp
- fur
- fy
- ga
- gan
- gd
- gl
- glk
- gn
- got
- gu
- gv
- ha
- hak
- haw
- he
- hi
- hif
- ho
- hr
- hsb
- ht
- hu
- hy
- hz
- ia
- id
- ie
- ig
- ii
- ik
- ilo
- io
- is
- it
- iu
- ja
- jbo
- jv
- ka
- kaa
- kab
- kg
- ki
- kj
- kk
- kl
- km
- kn
- ko
- kr
- ks
- ksh
- ku
- kv
- kw
- ky
- la
- lad
- lb
- lbe
- lg
- li
- lij
- lmo
- ln
- lo
- lt
- lv
- map_bms
- mdf
- mg
- mh
- mi
- mk
- ml
- mn
- mo
- mr
- mt
- mus
- my
- myv
- mzn
- na
- nah
- nap
- nds
- nds_nl
- ne
- new
- ng
- nl
- nn
- no
- nov
- nrm
- nv
- ny
- oc
- om
- or
- os
- pa
- pag
- pam
- pap
- pdc
- pi
- pih
- pl
- pms
- ps
- pt
- qu
- quality
- rm
- rmy
- rn
- ro
- roa_rup
- roa_tara
- ru
- rw
- sa
- sah
- sc
- scn
- sco
- sd
- se
- sg
- sh
- si
- simple
- sk
- sl
- sm
- sn
- so
- sr
- srn
- ss
- st
- stq
- su
- sv
- sw
- szl
- ta
- te
- tet
- tg
- th
- ti
- tk
- tl
- tlh
- tn
- to
- tpi
- tr
- ts
- tt
- tum
- tw
- ty
- udm
- ug
- uk
- ur
- uz
- ve
- vec
- vi
- vls
- vo
- wa
- war
- wo
- wuu
- xal
- xh
- yi
- yo
- za
- zea
- zh
- zh_classical
- zh_min_nan
- zh_yue
- zu
-