非離散系統中的可計算性和計算複雜性研究

《非離散系統中的可計算性和計算複雜性研究》是依託江蘇大學，由盧殿臣擔任項目負責人的面上項目。

基本介紹

• 中文名：非離散系統中的可計算性和計算複雜性研究
• 項目類別：面上項目
• 項目負責人：盧殿臣
• 依託單位：江蘇大學

項目摘要

在科學和工程計算中的各種套用問題的數學模型基本上都是非離散結構，而經典的可計算性和計算複雜性理論探討的則是離散結構中的計算問題。在實際的計算過程中，人們往往用離散的計算結果來逼近非離散問題的答案。然而，逼近過程中的誤差積累很可能會影響到計算結果的準確性。能性分析（Effective Analysis）就是要為此提供一種比較可行的解決方法。在本項目中我們將套用能行性分析的基本思想，深入地展開有關非離散系統中可計算性和計算複雜性的研究。鑒於絕大多數非離散系統的數學模型都是以實數為基礎的，我們將重點展開關於實數及實函式的可計算性及計算複雜性問題的探討。根據其可計算的程度，建立一種能行性分層。在此基礎上，我們還將系統探討實曲線的可計算性和計算複雜性問題。這將為各種運動軌跡的計算和分析提供新的理論基礎。本項目的研究旨在建立一個完整的可計算實數理論從而為非離散結構中的能行性研究奠定理論基礎。

結題摘要

本項目探討有關非離散系統中的可計算性和計算複雜性的問題。重點研究了下列兩類非離散結構：第一類是與實數相關的結構，如實變數函式和平面上的實曲線等。第二類結構是與各種偏微分方程解運算元有關的一類特殊的函式空間。最重要的研究方法是，充分利用已有的對實數，實函式，實曲線以及各類偏微分方程的數學研究成果，藉助於可計算分析中的表示理論，完成有關連續性個體的可計算和計算複雜性的研究。 對於第一類結構，我們把經典的可計算實函式的概念加以推廣。利用Cauchy表示的各種弱化，引進並系統地討論了弱可計算的實函式概念，使得對非連續性實函式的能行性探討成為可能。另外，我們探討了可計算實曲線的問題，並根據曲線的解析複雜性和計算複雜性，引進了相應的分層。由於實曲線是對粒子運動軌跡的自然描述，這種研究將在物理以及機器人研究領域會得到廣泛的套用。 為了研究微分方程解運算元的可計算性問題，我們套用了Weihrauch等創立的二類能行性理論框架，用表示理論的方法把可計算性概念引進到諸如Sobolov空間等函式空間中來。結合傅立葉變換、壓縮映像原理、索伯列夫空間的有關數學知識和技巧，證明了一大批具有套用價值的非線性偏微分方程的解運算元是可計算的。其中包括：KdV-Burgers方程，MKdV方程，GKdV方程，CKdV 方程，Schrödinger-Boussinesq方程，Coupled Schrödinger-Boussinesq方程，Nonlinear Heat Conduction 方程，Zakharov方程，Gardner方程，Camassa-Holm方程，Ostrovsky方程，Aceive方程，Klein-Gordon方程等。這些方程都是大量實際套用問題的數學模型，我們的研究將有助於為大量的工程計算和科學計算問題開發設計更為能行有效的算法和計算軟體。這些對各種方程解運算元可計算性的單獨討論，為我們下一步更為一致性的理論研究打下了很好的基礎。我們下一個目標將是試圖為各類微分方程解運算元的可計算性找出一種一致性的判別標準。 總之，在本項目的資助下，不僅讓我們解決了許多有關可計算性的重要的理論問題，更為重要的是，使我們有機會開闢了一個全新的研究新領域，即如何充分利用已有的純數學的研究成果，使之更好地套用到實際問題的計算過程中去。這將具有非常重要的科學意義和極其廣泛的實際套用價值。