What is known about the complexity of creating Block Designs (https://en.wikipedia.org/wiki/Block_design)?

I've found one paper that creates approximately solutions using Metaheuristics that claims that Block Design is NP-Hard, citing a paper from 1978. But that paper from 1978 makes no such claim or proof.

I'm particularly interested in the special case of Projective planes (https://en.wikipedia.org/wiki/Block_design#Projective_planes).

  • $\begingroup$ Complexity given what input? Just the number of vertices? All the parameters of the design? $\endgroup$ – Joshua Grochow Oct 18 '19 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.