《计算复杂性:现代方法》——2.6 coNP、EXP和NEXP

本节书摘来自华章计算机《计算复杂性:现代方法》一书中的第2章,第2.6节,作者 [美]桑杰夫·阿罗拉(Sanjeev Arora),博阿兹·巴拉克(Boaz Barak),译 骆吉洲,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

2.6 coNP、EXP和NEXP

现在,我们定义与P和NP相关的其他一些复杂性类。

2.6.1 coNP

《计算复杂性:现代方法》——2.6 coNP、EXP和NEXP
《计算复杂性:现代方法》——2.6 coNP、EXP和NEXP

2.6.2 EXP和NEXP

《计算复杂性:现代方法》——2.6 coNP、EXP和NEXP
《计算复杂性:现代方法》——2.6 coNP、EXP和NEXP