QCSP on Reflexive Tournaments.

Benoit Larose,Petar Markovic,Barnaby Martin,Daniel Paulusma,Siani Smith,Stanislav Zivny

ESA（2021）

引用 1|浏览28

暂无评分

摘要

We give a complexity dichotomy for the Quantified Constraint Satisfaction Problem QCSP(H) when H is a reflexive tournament. It is well-known that reflexive tournaments can be split into a sequence of strongly connected components H_1,...,H_n so that there exists an edge from every vertex of H_i to every vertex of H_j if and only if i更多

查看译文

关键词

Quantified constraints, constraint satisfaction, graph theorem, logic, computational complexity

AI 理解论文

溯源树

样例

生成溯源树，研究论文发展脉络

Chat Paper

正在生成论文摘要