9
$\begingroup$

In the following, we will describe what seems to be a parameterized version of the minimum circuit size problem (MCSP).

  • Before we get started, we need the following concepts:

For every natural number $n$, consider a function $B_n: [n] \rightarrow \{0,1\}^{\lceil \log(n) \rceil}$ such that $B_n(i)$ is the $i$th bit string in $\{0,1\}^{\lceil \log(n) \rceil}$ according to the lexicographical ordering. (Example: $B_7(5) = 100$)

Now, let a bit string $x$ of length $n$ be given. Let a boolean circuit $C$ with $\lceil \log(n) \rceil$ inputs and $1$ output be given. We say that $C$ computes $x$ if for every $i \in [n]$, $C(B_n(i)) = x_i$. In other words, $C$ computes $x$ one bit at a time.

  • Now, consider the following parameterized problem:

Given a bit string $x$ of length $n$ and a natural number $k$, does there exist a boolean circuit $C$ of size at most $k \log(n)$ that computes $x$?

If there are only $g(n,k)$ circuits of size $k\log(n)$, then we can solve this problem in roughly $n * k\log(n) * g(n,k)$ time by trying every possible circuit and evaluating each one on all $n$ inputs.

Question: What is the parameterized complexity of this problem?

This question has several parts:

  • Are any more efficient algorithms known?

  • Is this problem related to any standard parameterized complexity classes? For example, the problem could be $FPT$. Or, it could be $W[1]$-hard or harder.

  • Are there any known parameterized complexity results or conditional lower bounds for the minimum circuit size problem?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Nice question! It might depend on what you mean by the "size" of the circuit [whether you count gates or wires, or bit size in some way]. Seems very unlikely to be FPT to me... $\endgroup$
    – daniello
    Commented Mar 10, 2017 at 11:10
  • $\begingroup$ @daniello Thank you for the kind comment! I really appreciate it. :) $\endgroup$
    – Michael Wehar
    Commented Mar 10, 2017 at 17:41
  • 1
    $\begingroup$ In this case, $g(n,k) = n^k$ and we at least know that the problem lies in $XP$. Further, one could show that it lies in $W[P]$. But, I'm hoping someone out there might be able to show more. $\endgroup$
    – Michael Wehar
    Commented Mar 10, 2017 at 17:45
  • 1
    $\begingroup$ While this may not be a formal implication, it seems like the natural techniques to try to show that it is W[1]-hard would also show that MCSP is NP-hard, which is currently unknown (and some think unlikely). Would be nice to make the connection formal... $\endgroup$
    – Joshua Grochow
    Commented Nov 20, 2019 at 6:21
  • 2
    $\begingroup$ @JoshuaGrochow I finally had a chance to think about this. I think that if the above problem is W[1]-hard under parameter preserving reductions (defined in "Survey of parameter-preserving reductions" by Philipp Kuinke), then MCSP is NP-hard. $\endgroup$
    – Michael Wehar
    Commented Feb 10, 2020 at 21:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.