ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For each positive integer nn, consider the finite set of core trees with nn 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 fraction of core trees with n vertices that are NL-hard tends to 1 as n→∞.\text{The fraction of core trees with }n\text{ vertices that are NL-hard tends to }1\text{ as }n\to\infty.

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 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.