TournamentClique completeness conjecture for the second level of the polynomial hierarchy
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 , its directed clique number is the minimum, over all linear orders on , of the clique number of the corresponding backedge graph . The problem TournamentClique asks, given a tournament and a positive integer , whether . The class is the second level of the polynomial hierarchy. TournamentClique completeness conjecture. TournamentClique is -complete. This would settle the complexity of TournamentClique, which is already known to lie in ; 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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.