多元三次方程組可以在多項式時間內求解嗎？

據我所知，存在用於多元二次方程系統的多項式時間算法，例如，XL（擴展線性化）。但是我不知道是否存在一個多元三次方程組的一個多項式時間算法。有誰能爲我舉個例子嗎？非常感謝！多元三次方程組可以在多項式時間內求解嗎？

來源

2014-01-05 Jianting Wang

這個問題看似已關閉因爲它適合mathoverflow.net更好 –

@AlmaDo也許有點。它與編程沒有直接關係。但我認爲'算法'和'計算複雜性'也屬於這裏的主題。 –

只有當系統超定義時，XL纔會以多項式時間運行。

在一般情況下，在GF（2）上的多元非線性方程組的每個系統相當於一些3-SAT實例。因此，找到解決方案的難題是NP難。

我可以建議其他兩種方法，這是適用於一般的（在我的情況比XL快得多）：

來源

2014-01-05 15:43:46

謝謝！我會研究他們。 –

@JingingWang，如果你對這個話題有任何其他問題，請不要猶豫，直接問我。 –

我想我在描述中犯了一個錯誤，XL只能應用於二次方程。立方單項式之間存在類似的關係。也許在立方形式下它的複雜性不是多項式。 @max –

精確解

精確解的是，可用於找到方程係數根分析解決方案。即某種「公式」來解決問題。如果這是你的問題，那麼在一般情況下 - 沒有辦法 - 因爲Abel-Ruffini theorem說明了權力方程>=5方程的根：這些方程不能用代數數字（即用偏旁部分寫）解決。即使對於來自兩個三次方程的系統，您也將面對這樣的等式。

近似解

要做到這一點，你可以使用root finding algorithms之一，例如，Aberth's方法 - 但你應該知道它的複雜性無法輕易推算，如果表現都非常的問題，然後看看fast Fourier transform。

來源

2014-01-05 15:18:19

多元三次方程組可以在多項式時間內求解嗎？

回答

相關問題