Asymptotic NL-hardness conjecture for core trees
Statement
For each positive integer , consider the finite set of core trees with vertices, meaning oriented trees whose only endomorphisms are automorphisms. Let the fraction of these trees that are NL-hard be measured uniformly. Asymptotic NL-hardness conjecture.
The conjecture is suggested by the computational data in the paper. No proof or disproof is supplied, so its asymptotic status 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.