Suposição sobre pesos em circuitos limiares

Uma porta de limite que implementa uma função de limite linear em entradas booleanas é dada pela equação: onde . Os são chamados de pesos da função de limiar e é chamado de limiar e, naturalmente, o gate dispara na entrada se a soma ponderada dada pela equação acima exceder .$n$$x_1, x_2 \ldots, x_n$$w_1 x_1 + w_2 x_2 + \ldots, w_n x_n \ge t$$w_1, \ldots, w_n, t \in \mathbb{R}$$w_i$$t$$1$$x$$t$

Agora, em quase toda a literatura sobre circuitos limiares, encontro esse fato (que acho que é folclore, pois não consegui encontrar uma prova em lugar algum): Os na equação linear acima podem ser feitos inteiros (em bits), e um circuito de limiar composto por esses portões ainda calculará o que for possível com pesos reais. Pensei nisso e acho que deve ser um truque simples, mas não consegui obter uma prova desse fato. Alguém pode me ajudar ou me fornecer uma referência? (a única referência que encontrei foi um texto de Muroga, que não consegui obter)$w_i$$n \log{n}$

Dado $w_1,\ldots,w_n,t$, deixei $X$ ser o conjunto de atribuições que $\sum_i w_i x_i \geq t$e considere o programa linear com variáveis $z_1,\ldots,z_n$ e a $2^n$ restrições

$$\begin{align*} \sum_i z_i x_i \geq +1 & (x_1,\ldots,x_n) \in X \\ \sum_i z_i x_i \leq -1 & (x_1,\ldots,x_n) \notin X \end{align*}$$ Este programa linear (com uma função objetivo constante) é viável (desde que $z_i = w_i/t$ é uma solução), e também tem uma solução $z_1,\ldots,z_n$que é um vértice. Como tal, é a solução de um sistema de$n$ equações da forma $$\sum_i z_i x_i = \pm 1.$$ Regra de Cramer dá a cada $z_i$ como uma proporção de dois $n \times n$ determinantes de matrizes de $0,\pm 1$entradas; de fato, o denominador é o mesmo. Cada numerador$N_i$ e o denominador comum $D$ é no máximo $n!$ em magnitude, multiplicando tudo por $D$, obtemos uma solução integral $N_1,\ldots,N_n,D$, onde todas as quantidades são no máximo $n! \leq n^n = 2^{n\log n}$ em magnitude.