0
$\begingroup$

Let's say that we have a decision problem $P$. Let's also say that $I_n$ is the set of all instances of size $n$ that exist for this problem, and that its cardinality is finite.

There is a sequence of bits that uniquely represents each instance (of that size) of the problem. Each of these sequences has $b(n)$ bits (for the sake of simplicity, let's say that $b$ is a linear function, but it could also be polynomial, exponential or even double exponential, depending on the problem). We could say, for example that all instances of size 4 are represented with 8 bits, instances of size 5 are represented with 10 bits, etc... The bits are completely independent of each other: there are no cases in which any information about the value of a bit can be obtained from another bit. Also, for each configuration of those bits, there is a corresponding instance of the problem. There are no two configurations which represent the same instance of the problem and there is no configuration that does not represent a problem. So, let's say that there is a bijection between configurations of those $b(n)$ bits and instances of size $n$. We had previously said that the cardinality o $I_n$ is finite, but now we can even say that $|I_n| = 2^{b(n)}$, since that is the number of possible configurations for a sequence of $b(n)$ bits, and each configuration corresponds to an instance of the problem.

For each $n \in \mathbb{N}$, there exists a circuit $C_n$ that receives $b(n)$ bits as its input and outputs the result ($1$ for YES, $0$ for NO) of the corresponding instance of problem $P$. I don't know if it is relevant to my question, but these circuits use only $AND$ and $OR$ gates. Also, let's say that "creating"/"describing" the circuit for size $n$ can be done in $O(n)$ for this particular problem $P$.

My question is: Given the circuit $C_n$ can we find an equivalent circuit $C^{\prime}_n$ which is optimal, or can we derive some information about the circuit complexity of the problem $P$? In this context we will say that a circuit is optimal if it has the least possible number of gates that is required to compute the corresponding boolean function.

My instincts tell me that we should be able to use Quine-McCluskey to find an optimal equivalent circuit (even if doing so would be unfeasible for large $n$), and that we could establish lower bounds for the circuit complexity of the problem $P$ by looking at the way in which the size and depth of the circuit $C^{\prime}_n$ changes as $n$ increases. However, it also seems like this would be "too easy" and that there must be a reason why it does not work that way.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The problem is $\Sigma_2^P$-complete, which means that it is hard -- it is even "harder" than NP-complete problems. In particular, there is unlikely to be any polynomial-time algorithm. See https://en.wikipedia.org/wiki/Logic_optimization#Boolean_expression_minimization.

However, there are many heuristic methods. See https://en.wikipedia.org/wiki/Logic_optimization.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for your answer. I understand that finding an equivalent optimal circuit is complex and will probably not be feasible for a large n. Assuming that it could be done in constant time (just for the sake of the argument), would it be useful to compute this optimal circuits to establish lower bounds for the circuit complexity of the problem P? $\endgroup$
    – Alonso Montero
    Commented Apr 10, 2023 at 18:07
  • 1
    $\begingroup$ @AlonsoMontero, no, because circuit complexity is an asymptotic notion, and you can only compute lower bounds for finitely many circuits, which will not prove anything about asymptotic bounds. $\endgroup$
    – D.W. ♦
    Commented Apr 10, 2023 at 23:40
  • $\begingroup$ Ok, just to make sure that I am understanding correctly: If there was a proof that showed that, for all $n \in \mathbb{N}$, the corresponding $C_n$ will be reduced (by Quine-McCluskey or some equivalent method) to a circuit $C^{\prime}_n$ of size $f(n)$ (again, for the sake of the argument, let's say that $f$ is something simple like a quadratic function), then I would be able to make a statement about the circuit complexity of these circuits, right? I think that in that case, it would even be possible to indicate the exact complexity, which would be described by $f$. Is that right? $\endgroup$
    – Alonso Montero
    Commented Apr 11, 2023 at 0:49
  • 1
    $\begingroup$ @AlonsoMontero, yup, assuming you use a version of Quine-McCluskey thatis guaranteed to give the smallest circuit, because then you have a proof that the smallest circuit for each $n$ has size $f(n)$. That's unlikely to be feasible in practice, though, for most interesting circuits. $\endgroup$
    – D.W. ♦
    Commented Apr 11, 2023 at 2:43
  • $\begingroup$ OK, thanks for the input. I am not so interested in doing this a I am in understanding that it could theoretically be done. Just one more question: I have assumed that the "standard" version of Quine-McCluskey (the one that is described in Wikipedia) will give the smallest possible circuit that decides the problem. Is that not the case? $\endgroup$
    – Alonso Montero
    Commented Apr 11, 2023 at 14:56

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.