复杂类co-NP中的团决策问题吗?

问题描述 投票:0回答:0

co-NP中的团决策问题吗?

定义:

“在clique决策问题中,输入是一个无向图和一个数字k,输出是一个布尔值:如果图中包含k-clique,则为true,否则为false。” (https://en.wikipedia.org/wiki/Clique_problem

“如果只有非实例具有多项式长度的“证书”并且存在可用于验证任何声称的证书的多项式时间算法,则 co-NP 中存在决策问题。” (https://en.wikipedia.org/wiki/Co-NP

graph-theory complexity-theory clique-problem
© www.soinside.com 2019 - 2024. All rights reserved.