课题基金 / 基金详情

Derandomisierung von Polynomgleichungen

Derandomisierung von Polynomgleichungen
多项式方程的去随机化
批准号:
5423284
负责人:
Professor Dr. Uwe Schöning
金额:
$0.0万
依托单位国家:
德国
项目类别:
Research Grants
财政年份:
2004
资助国家:
德国
项目状态:
已结题
起止时间:
2003-12-31 至 2009-12-31

项目摘要

项目成果

Professor Dr. Uwe Schöning的其他基金

相似基金

相关文献

中文摘要
翻译
Viele algorithmischen (Entscheidungs-) problem - lassen simetisien,又称in System von polynomial gleichungen bersetzen, so dass die Aufgabe letztlich darin best, eine solche (multi-variate) polynomial gleichung zu berpre<e:1>。大比例尺(problemabhängig)是这样的,多项式之间的函数可以显式地表示出正则表达式,现代函数可以隐式地表示形式正则表达式,zum Beispiel图,行列式矩阵可以显式地表示出Schaltkreis。研究人员对该方法进行了分析,并对其进行了随机分析。大北werden zufallsswerte in die (implizit gegebenen);多义性(polyonomene);和den zufallssteellen ausgewertet [Sch80, Zip79]。[2]张建军,张建军,张建军,等。动力动力系统与动力系统研究进展[j]。我们还发现,这种算法也可以被称为“随机算法”,也可以被称为“多项式算法”,可以被称为“随机算法”,也可以被称为“快速算法”。Ziel dieses项目列表,die Methoden von AKS auf andere, ähnlich gelagerte problem, wie beispielwise perfect Matching, odder das Äquivalenzproblem fsr read-once branching Programme zu bertragen。
英文摘要
Viele algorithmischen (Entscheidungs-) Probleme lassen sich arithmetisieren, also in ein System von Polynomgleichungen übersetzen, so dass die Aufgabe letztlich darin besteht, eine solche (multi-variate) Polynomgleichung zu überprüfen. Dabei ist es problemabhängig oft so, dass die betreffenden Polynome nicht explizit gegeben sind, sondern nur in einer impliziten Form vorliegen, zum Beispiel als Graph, Determinante einer Matrix oder als Schaltkreis. Eine oftmals angewandte Methode besteht darin, ein randomisiertes Verfahren anzuwenden. Dabei werden Zufallswerte in die (implizit gegebenen) Polynome eingesetzt und diese an den Zufallsstellen ausgewertet (Sch80, Zip79]. Ausgangspunkt und Motivation für dieses Projekt ist die effiziente Lösung des Primzahlproblems, welche von Agrawal, Kayal und Saxona [AKS02] angegeben wurde. Es stellt sich heraus, dass dieser Algorithmus als eine derandomisierte Version eines Polynomgleichungstests, wie oben beschrieben, aufgefasst werden kann. Ziel dieses Projektes ist es, die Methoden von AKS auch auf andere, ähnlich gelagerte Probleme, wie beispielsweise Perfektes Matching, oder das Äquivalenzproblem für read-once branching Programme zu übertragen.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Stochastische Lokale Suche bei SAT-Solvern
Basic investigations about aspects of entropy in algorithms and algorithmic processes
Probabilistische Algorithmen und Methoden in der Logik
国内基金
海外基金
半有限von Neumann代数中投影集上的Wigner定理
  • 批准号:
  • 项目类别:
    省市级项目
  • 资助金额:
    --
  • 批准年份:
    2025
  • 负责人:
    钱文华
  • 依托单位:
CUL7基因突变导致Von Hippel Lindau蛋白细胞内蓄积增多致3-M综合征软骨细胞分化异常的分子机制研究
  • 批准号:
    82302106
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    30万元
  • 批准年份:
    2023
  • 负责人:
    石伟哲
  • 依托单位:
非交换Weyl-von Neumann定理及其弱形式在von Neumann代数中的拓展
  • 批准号:
    12271074
  • 项目类别:
    面上项目
  • 资助金额:
    45万元
  • 批准年份:
    2022
  • 负责人:
    石瑞
  • 依托单位:
线性保持方法在量子信息研究中的应用
  • 批准号:
    12001420
  • 项目类别:
    青年科学基金项目
  • 资助金额:
    24.0万元
  • 批准年份:
    2020
  • 负责人:
    王美丽
  • 依托单位: