课题基金 / 基金详情

Computational complexity, topology, and singularities

Computational complexity, topology, and singularities
计算复杂性、拓扑和奇点
批准号:
5379865
负责人:
Professor Dr. Peter Bürgisser
金额:
$0.0万
依托单位:
依托单位国家:
德国
项目类别:
Research Grants
财政年份:
2002
资助国家:
德国
项目状态:
已结题
起止时间:
2001-12-31 至 2005-12-31

项目摘要

项目成果

Professor Dr. Peter Bürgisser的其他基金

相似基金

相关文献

中文摘要
翻译
几何算法、拓扑算法、组合算法、结构算法、代数算法、几何算法、代数算法、几何算法、几何算法、代数算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、几何算法、代数算法。Diese Idee wurde von Strassen mit hilife des algebraisch-geometrischen Grad erstmals erfolgrerich in die . [endnogeetzt Durch Arbeiten von Ben-Or, Björner, Lovász] and Yao ist bekant, ass每个拓扑的invariant和Bettizahlen unterere Schranken liefern。Diese Schranken wurden bisher fast ausschließlich auf lineare problem (arrangement) angewandt。在weiterer Ansatz zur Verwendung拓扑不变量得到ausmale和Vassiliev zur<s:1> ck。In diesem forschungsvohaben möchte der Antragsteller die Tragweite topologcher Methoden fr den Beweis unterer Komplexitätsschranken systematisch ausloten。Zunächst soll geklärt werden, inwieweit die bereits vorgeschlagenen Schranken bei nichtlinearen problem greifen。大足之学,verfaren之学。weiterzuentwickeln, welche die Bettizahlen spezifischer singulärer algebraischer Varietäten berechnen。在einem zweiten Schritt sollen schwendung werden中,Verwendung werden的意思是:“在einem zweiten Schritt sollen schwendung werden”。weiterin soll untersucht werden, in welchem Umfang die gewonnenen Schranken in randomisiten Berechnungsmodellen gtigbleiben。
英文摘要
Eine komplizierte geometrische, topologische oder kombinatorische Struktur eines algebraischen Berechnungsproblems kann oft als Ursache für eine grosse algorithmische Komplexität identifiziert werden. Diese Idee wurde von Strassen mit Hilfe des algebraisch-geometrischen Grad erstmals erfolgreich in die Tat umgesetzt Durch Arbeiten von Ben-Or, Björner, Lovász und Yao ist bekannt, dass auch topologische Invarianten wie Bettizahlen untere Schranken liefern. Diese Schranken wurden bisher fast ausschließlich auf lineare Probleme (Arrangements) angewandt. Ein weiterer Ansatz zur Verwendung topologischer Invarianten geht auf Smale und Vassiliev zurück. In diesem Forschungsvorhaben möchte der Antragsteller die Tragweite topologischer Methoden für den Beweis unterer Komplexitätsschranken systematisch ausloten. Zunächst soll geklärt werden, inwieweit die bereits vorgeschlagenen Schranken bei nichtlinearen Problemen greifen. Dazu sind Verfahren zu studieren bzw. weiterzuentwickeln, welche die Bettizahlen spezifischer singulärer algebraischer Varietäten berechnen. In einem zweiten Schritt sollen durch Verwendung feinerer Invarianten neue untere Schranken mit neuen Anwendungen erschlossen werden. Weiterhin soll untersucht werden, in welchem Umfang die gewonnenen Schranken in randomisierten Berechnungsmodellen gültig bleiben.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Geometry and representation theory in computational complexity
  • 批准号:
    121425861
  • 项目类别:
    Priority Programmes
  • 资助金额:
    $0.0万
  • 财政年份:
    2009
  • 负责人:
    Professor Dr. Peter Bürgisser
  • 依托单位:
Geglättete Analyse von Konditionszahlen
  • 批准号:
    40997669
  • 项目类别:
    Research Grants
  • 资助金额:
    $0.0万
  • 财政年份:
    2007
  • 负责人:
    Professor Dr. Peter Bürgisser
  • 依托单位:
海外基金