-1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Kaveh Sep 23 '12 at 7:06
  • 1
    $\begingroup$ @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. $\endgroup$ – Kristoffer Arnsfelt Hansen Sep 23 '12 at 13:08
  • $\begingroup$ @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. $\endgroup$ – Kaveh Sep 23 '12 at 20:27
2
$\begingroup$
  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 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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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