<ol>
<li>There is fundamentally little difference between positive and negative weights. It just corresponds to negating the corresponding input. (i.e. replacing $x_i \in \{0,1\}$ by $(1-x_i$)).</li>
<li>Yes. It was shown by <a href="http://dx.doi.org/10.1016/0016-0032%2861%2990702-5" rel="nofollow">Muroga, Toda and Takasu</a> that integer weights of magnitude $(n+1)^{(n+1)/2}/2^n$ are sufficient.</li>
<li>I don't know about this (is there a reason for this question by the way?). However one can assume that weights are even integers of magnitude at least 4, and such numbers can be written as the sum of at most 6 primes. Hence any threshold function on $n$ variables is a <em>projection</em> of a threshold function on at most $6n$ variables where all weights are prime numbers (or the negative of prime numbers). So it would be reasonable to say that threshold functions with prime weights are as powerful as threshold functions with no such restriction.</li>
</ol>

CC BY-SA 3.0
2012-09-23T13:05:54.510Z
2012-09-23T13:05:54.510Z
Kristoffer Arnsfelt Hansen
<p>I have the following questions about the weights used in threshold circuits: </p>

<ol>
<li><p>What is the difference beween real weight and non-negative real one? </p></li>
<li><p>Integer weights can efficiently simulate real weights ? </p></li>
<li><p>Certain kind of integer like prime numbers has as powerful as general integer weights?</p></li>
</ol>

CC BY-SA 3.0
2012-09-23T07:06:20.673Z
we can always round a threshold value to an integer, can't we? $r \leq k$ iff $\lceil r \rceil \leq k$ ($k$ is an integer).
Kaveh
CC BY-SA 3.0
2012-09-23T13:08:22.653Z
@Kaveh: It is slightly more complicated than that: Since the input domain is finite and integral we can perturb the weights slightly in order to make them rational numbers without altering the Boolean function computed. Now we can just clear denominators.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-09-23T20:27:58.870Z
@Kristoffer, I misread the question. I thought it is about the threshold value of the gate, not about the weights put on the inputs. I would also be interested in knowing the motivation.
Kaveh
<cc.complexity-theory><circuit-complexity>
Weights in threshold circuits
JUly
# Weights in threshold circuits

(Asked by: username_0 on 2012-09-23)

I have the following questions about the weights used in threshold circuits:

1. What is the difference beween real weight and non-negative real one?
2. Integer weights can efficiently simulate real weights ?
3. Certain kind of integer like prime numbers has as powerful as general integer weights?

**Tags:** cc.complexity-theory, circuit-complexity

> **Comments:**
> **username_1**: we can always round a threshold value to an integer, can't we? $r \leq k$ iff $\lceil r \rceil \leq k$ ($k$ is an integer).  
> **username_2**: @username_1: It is slightly more complicated than that: Since the input domain is finite and integral we can perturb the weights slightly in order to make them rational numbers without altering the Boolean function computed. Now we can just clear denominators.  
> **username_1**: @Kristoffer, I misread the question. I thought it is about the threshold value of the gate, not about the weights put on the inputs. I would also be interested in knowing the motivation.  

---

## 1 answers

### Answer by username_2 on 2012-09-23. Score: 2

1. There is fundamentally little difference between positive and negative weights. It just corresponds to negating the corresponding input. (i.e. replacing $x\_i \in \{0,1\}$ by $(1-x\_i$)).
2. Yes. It was shown by [Muroga, Toda and Takasu](http://dx.doi.org/10.1016/0016-0032%2861%2990702-5) that integer weights of magnitude $(n+1)^{(n+1)/2}/2^n$ are sufficient.
3. I don't know about this (is there a reason for this question by the way?). However one can assume that weights are even integers of magnitude at least 4, and such numbers can be written as the sum of at most 6 primes. Hence any threshold function on $n$ variables is a *projection* of a threshold function on at most $6n$ variables where all weights are prime numbers (or the negative of prime numbers). So it would be reasonable to say that threshold functions with prime weights are as powerful as threshold functions with no such restriction.


---

