# Questions tagged [circuits]

A computation model in which the computation is described via circuits of various logic gates.

296 questions
Filter by
Sorted by
Tagged with
58 views

### Can you compute a majority function of n-bits using an O(n) size circuit?

Are you able to construct a boolean circuit that computes the majority function of n bits where the circuit only takes up O(n) space? If so, what would that circuit look like? I have a feeling it has ...
706 views

### Representing binary functions with a finite gate set without exponential blow-up?

It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the ...
11 views

1 vote
20 views

### Why is End-Of-The-Line defined in terms of "Arithmetic circuits" instead of "Boolean circuits"

The definition of PPAD (Polynomial parity arguments on directed graphs) revolves around the definition of "End-Of-The-Line" An exponentially large polynomial-depth arithmetic circuit, $f$, ...
26 views

### Representing classical circuits with quantum gates

Many problems in computer science input boolean circuits to problems. Just as a toy example, let's define the below problem to be called $A$: Given a polynomial depth circuit with $N$ bits of output, ...
32 views

### "Succinct circuit representation" on Turing machines?

The famous PPAD class revolves around the End-Of-The-Line problem. Basically, it states that you are given two polynomial depth circuits, $P$ and $Q$, which act as "possible previous" and &...
36 views

### How to convert loop into combinational circuit?

In high-level programming languages, such as C and Python, loop statements such as while and ...
1 vote
59 views

### Acyclic boolean circuit (DAG)

If a function f has a while loop or for loop, can I compile this function into an ...
1 vote
27 views

### Suggestion for tools/libraries for multi-output boolean circuit minimization?

I am interested in the following problem Input: A boolean function F with n boolean inputs and m boolean outputs. Output: A circuit C implementing F such that C has as few gates as possible. The ...
45 views

### How do I create a circuit based on this truth table? The solution I implemented is not working as expected

I am trying to create a circuit based on this truth table below: can you describe how to make the circuit using only logic gates ...
47 views

### Can an arithmetic circuit have multiple outputs?

An arithmetic circuit relates to calculating the value of a polynomial given some inputs. But is it still considered a circuit if the DAG corresponds to the evaluation of multiple polynomials that ...
1 vote
51 views

### Time complexity when implementing uniform family of circuits

It is known that the complexity class P is equivalent to the class of problems decided by polynomial-time uniform familiy of circuits. When stating the complexity of algorithms as this family of ...
1 vote
47 views

### Can Boolean circuits of polylog depth represent all Boolean functions?

Consider a Boolean circuit using (2-input) logical-and, (2-input) logical-or and logical-not as basic components. The depth of the Boolean circuit is the length of the longest path from the input to ...
611 views

### Shannon's result that some Boolean functions require exponential circuits

In 1949 Shannon proved, using a non-constructive counting argument, that some boolean functions have exponential circuit complexity, see  and many texts on computational complexity. This result has ...
1 vote
### prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$
I need to prove that if $SAT\notin Size(2^{n/100})$ then CorrectSATSolver$\in P$. Where CorrectSATSolver $= \{C | C(\varphi) = 1 \iff \varphi$ is satisfiable$\}$. In other words, CorrectSATSolver ...