TournamentClique completeness conjecture for the second level of the polynomial hierarchy

A tournament is a directed graph in which exactly one of the two possible directions is chosen for every pair of distinct vertices. For a tournament TT, its directed clique number ω(T)\operatorname{\overrightarrow{\omega}}(T) is the minimum, over all linear orders \ll on V(T)V(T), of the clique number of the corresponding backedge graph TT^\ll. The problem TournamentClique asks, given a tournament TT and a positive integer tt, whether ω(T)t\operatorname{\overrightarrow{\omega}}(T)\leq t. The class Σ2P\Sigma^\mathsf{P}_2 is the second level of the polynomial hierarchy. TournamentClique completeness conjecture. TournamentClique is Σ2P\Sigma^\mathsf{P}_2-complete. This would settle the complexity of TournamentClique, which is already known to lie in Σ2P\Sigma^\mathsf{P}_2; the conjectured hardness remains open.

Sources & referencesView supporting material

Primary source

Grzegorz Gutowski and Mikołaj Rams, “A Note on the Complexity of Directed Clique”, arXiv:2602.11773 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.