<p>What is known about the complexity of creating Block Designs (<a href="https://en.wikipedia.org/wiki/Block_design" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Block_design</a>)?</p>

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

<p>I'm particularly interested in the special case of Projective planes (<a href="https://en.wikipedia.org/wiki/Block_design#Projective_planes" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Block_design#Projective_planes</a>).</p>

CC BY-SA 4.0
2019-10-18T17:22:53.630Z
Complexity given what input? Just the number of vertices? All the parameters of the design?
Joshua Grochow
CC BY-SA 4.0
2020-04-30T05:44:43.117Z
Given any of the above. Happy with either complexity of specific classes or more general  results. In particular, any classes that are know to be NP-hard as claimed by previous papers.
Wayne
CC BY-SA 4.0
2020-04-30T16:39:05.930Z
It would help if you could include a link to the paper "that creates approximately solutions using metaheuristics". Perhaps they meant to refer to a different paper? But it is hard to tell without seeing it.
Joshua Grochow
<cc.complexity-theory><np-hardness><combinatorics>
Complexity of Block Design?
Wayne
# Complexity of Block Design?

(Asked by: username_0 on 2019-10-18)

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

**Tags:** cc.complexity-theory, np-hardness, combinatorics

> **Comments:**
> **username_1**: Complexity given what input? Just the number of vertices? All the parameters of the design?  
> **username_0**: Given any of the above. Happy with either complexity of specific classes or more general  results. In particular, any classes that are know to be NP-hard as claimed by previous papers.  
> **username_1**: It would help if you could include a link to the paper "that creates approximately solutions using metaheuristics". Perhaps they meant to refer to a different paper? But it is hard to tell without seeing it.  

---

## 0 answers

