以解构造整数多项式方程

zeroieme

首先限定多个变量\(\left[x_1,x_2,\ldots,x_m\right]\)每个变量只能取值为0或1。
然后为给定若干个解  \(X_1=\left[x_1=a_{1,1},x_2=a_{1,2}, \ldots ,x_m=a_{1,m}\right],\)\(\ldots\)\(X_n=\left[x_1=a_{n,1},x_2=a_{n,2},\ldots,x_m=a_{n,m}\right]\)  构造一个整数多项式。

简单例子
\(\left\{\left\{x_1,x_2,x_3\right\}=\{1,0,1\},\left\{x_1,x_2,x_3\right\}=\{0,1,0\},\left\{x_1,x_2,x_3\right\}=\{1,1,1\},\left\{x_1,x_2,x_3\right\}=\{1,1,0\}\right\}\)
简单粗暴的办法是\(\left(4 x_1+2 x_2+x_3-7\right) \left(4 x_1+2 x_2+x_3-6\right) \left(4 x_1+2 x_2+x_3-5\right) \left(4 x_1+2 x_2+x_3-2\right)=0\)
如果利用\(\left(1-x_i\right) x_i\)求余可得\(-36 x_2 x_1+24 x_2 x_3 x_1-26 x_3 x_1+36 x_1+35 x_2-23 x_2 x_3+25 x_3-35=0\)

能简化到一次方程吗？而且对于更多变量，上述粗暴方法也不管用了。




不能简化到一次方程，方程组也可以

补充内容 (2020-8-18 12:03):
用几何思维，解域为0-1就是n维空间下超立方体的顶点，线性方程至多是n-1维的超平面。

.·.·.

你在想什么？
直接把全部x1+x2+...+xm-a1-a2-...-am乘起来不好吗？
至于一次，一次肯定不行啊

zeroieme

.·.·. 发表于 2020-8-15 21:56
你在想什么？
直接把全部x1+x2+...+xm-a1-a2-...-am乘起来不好吗？
至于一次，一次肯定不行啊

在0-1解域下\((a+2 b+4 c+8 d-15) (a+2 b+4 c+8 d-12) (a+2 b+4 c+8 d-3) (a+2 b+4 c+8 d)=0\)
与
\(384 a b c d-192 a b c-192 a b d+142 a b-192 a c d+164 a c+40 a d-77 a-192 b c d+220 b c-40 b d-65 b-368 c d+88 c+280 d=0\)
与\((a-b)+4 (c-d)=0\)是同解的。
当然这是我构造的，而且我不会逆算。


简单的说是想把逻辑运算线性化。

hujunhua

.·.·. 发表于 2020-8-15 21:56
你在想什么？
直接把全部x1+x2+...+xm-a1-a2-...-am乘起来不好吗？
至于一次，一次肯定不行啊

这样肯定不同解呀，xi, xj可两两交换了，可能产生 m!-1 个增根。

.·.·.

zeroieme 发表于 2020-8-15 22:09
在0-1解域下\((a+2 b+4 c+8 d-15) (a+2 b+4 c+8 d-12) (a+2 b+4 c+8 d-3) (a+2 b+4 c+8 d)=0\)
与
\( ...

如果这样我大概明白了

然而问题是

0-1规划好像是个NPC问题
就算你构造出方程，你也得不到（一般的）解法

mathe

主要是你的简化目的不是很明确，不明白你到底要怎么样的结果。
比如你顶楼的例子中，四个向量可以用四个一次多项式的乘积达到目的。是不是希望次数能够尽量低一些？
那么我们首先必然可以找出一个一次多项式满足前两个向量，而且第三个向量是前两个的线性组合，于是这个一次多项式或同时满足前三个向量。
然后再找一个满足第四个向量的多项式，最后两个多项式相乘即可。

mathe

当然正常情况一次多项式肯定是不行的，除非给出的所有向量之间本身线性相关。
还要看你的向量数目和向量的维数n之间的关系。
比如向量数目小于n，那么必然可以找出一个一次多项式同时满足它们。
如果向量数目大于n但是小于n(n+1)/2,可以考虑对于每个向量计算出"扩展向量"
x1,x2,...,xn,x1x2,x1x3,...,x1xn,x2x3,...,x2xn,....,x{n-1}x_n
然后必然可以在这个“扩展向量”的空间中找出一种让它们线性组合为0的方案，对应到原向量空间就是一个二次多项式。
当然，这个计算量在向量数目很大时是很困难的

zeroieme

mathe 发表于 2020-8-16 07:13
主要是你的简化目的不是很明确，不明白你到底要怎么样的结果。
比如你顶楼的例子中，四个向量可以用四个一 ...

我的目的是把四个向量作为解构造出一个多项式方程或者方程组。
顶楼是我的一个不太成功的办法。


看3#
\(\{\{a= 0,b= 0,c= 0,d= 0\},\{a= 0,b= 0,c= 1,d= 1\},\{a= 1,b= 1,c= 0,d= 0\},\{a= 1,b= 1,c= 1,d= 1\}\}\)
用顶楼的办法得到一个4次方程，但其实有一个简单的1次方程。

zeroieme

mathe 发表于 2020-8-16 07:13
主要是你的简化目的不是很明确，不明白你到底要怎么样的结果。
比如你顶楼的例子中，四个向量可以用四个一 ...

如果期望次数能够尽量低，那么向量数目小于n的方法是怎样的？至少我可以把向量分成n-1个一组分别算出一次方程。