Keevash–Knox–Mycroft complexity conjecture for dense hypergraph perfect matchings
Statement
Let be a -graph on vertices, and let be its minimum -degree. Define to be the decision problem of determining whether a -graph on vertices with minimum -degree at least has a perfect matching; write . A problem is in if it can be solved in polynomial time.
Keevash–Knox–Mycroft conjecture. The decision problem
is in for every .
This conjecture concerns the transition from NP-completeness below the space-barrier threshold to polynomial-time solvability above it. The paper states that the conjecture was verified in a range of cases using its main theorem, but does not establish it in full generality.
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.