Co language

Co language

這文章主要是想講Co language 和  co-NP，還有一些推論，鑒於我最近在讀complexity theory:
也做了一些筆記，希望可以分享給大家。

給一個decision problem的集合，可以定義這個集合的 "co":
首先先講一下定義: 還有一些基本性質><，還有他和其他的complexity class 的關係:
Given any complexity class, one can try to define co-that complexity class

Go back to Main page Notes for Complexity theory

比方像是這個 class 和 P, EXP, NP 等關係: 基本上用到一些很簡單的集合論而已
Just some simple techniques, one can show some basic theorems about these complexity class.

結束這些看起來抽象的定義以後: 應該要找一些真正的屬於 co-NP 的問題。
首先介紹 
After presenting some abstract proof, one should look for some questions belonging to co-NP

(1)Perfect matching.

Finally I try to present Prett's theorem.
Whether a number is a prime number belongs to NP and also belongs to co-NP.
I followed "CS681 Computational Number Theory Lecture 17: Primality is in NP ∩ coNP Instructor: Piyush P Kurur Scribe: Ramprasad Saptharishi"





Corollary: Factoring belongs to NP and belongs to co-NP
Most people believed that factoring belongs  to P. Quantum computing and Shor's algorithm become interesting in this class.
Indeed, Factoring belongs to BQP.