ProbXiv
Explorersign in
Problem archiveProblem record

Statement

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 T≪T^\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.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.