Mathematical Sciences: Frequency Approach to Approximating Algorithms

数学科学：近似算法的频率方法

• 批准号: 9210443
• 负责人: Valentina Harizanov
• 金额: $ 1.76万
• 依托单位: George Washington University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1992
• 资助国家: 美国
• 起止时间: 1992-08-01 至 1994-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9210443&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Frequency; Approach; Approximating

The proposed research revolves around two general questions: 1) Complete classification of problems according to which frequency algorithms they are amenable; and 2) Complete understanding of the of the recursion-theoretic properties of frequency computable problems. Computing, as it is practiced today, is of an interactive nature. Rather than the model of twenty years ago, where the computer was presented with a program and ran until it obtained an answer, the programs of today pause frequently and ask for input before continuing. Thus the true model of computing, as it is practiced, is the Turing machine with an oracle.

拟议的研究围绕着两个一般性问题： 1)问题的完整分类， 频率算法，他们是顺从的;和2）完整的 的递归理论性质的理解 频率可计算问题。 正如今天所实践的那样，计算是一种交互式的 自然 而不是20年前的模式， 计算机被提交了一个程序并运行，直到它获得 一个答案，今天的节目经常暂停，并要求 在继续之前输入。 因此，真正的计算模型，因为它 是一个有神谕的图灵机。