I think that a table with the following numeric values would be very interesting, but I could not find any table online displaying them:

Choose any NP-complete problem (say, clique, but a problem having well defined instances of $n$-bit size for every $n$ is probably best for this question). For each value of $n$ (input size), there is a minimum size boolean circuit that solves the problem for instances of size $n$. It is obviously computationally hard to actually compute these minimum sizes, but they can be computed by exhaustive search for small values of $n$.

Is there any table of such values for small $n$ known?

  • $\begingroup$ Not a boolean circuit, but interesting nonetheless. The minimal size sorting circuit for $n$ inputs. $\endgroup$ – orlp Mar 31 '20 at 22:24

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.