One-Way Functions and Polynomial Isomorphisms

单向函数和多项式同构

• 批准号: 9108899
• 负责人: Jie Wang
• 金额: $ 3.35万
• 依托单位: Wilkes University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-09-01 至 1994-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9108899&HistoricalAwards=false
• 关键词: Way; Functions; Polynomial; Isomorphisms

This research aims to better understand the relationships between the existence of one-way functions and the polynomial isomorphisms of complete sets for complexity classes using the idea of polynomial creativity. In particular, the goal is to explore a reasonable condition on one-way functions that implies non-isomorphisms. Early approaches to this problem, under the assumption that certain strong one-way functions exist, either turn out a trivial proof or require that the definition of one-way functions be dependent on a particular complete set. The approach in this project uses recent results and methods of polynomial creativity.

本研究旨在利用多项式创造性的思想来更好地理解复杂类的单向函数的存在性与完备集的多项式同构之间的关系。特别地，我们的目标是探索单向函数的一个合理条件，该条件蕴含着非同构。解决这个问题的早期方法，在假设某些强单向函数存在的情况下，要么给出一个平凡的证明，要么要求单向函数的定义依赖于特定的完备集。这个项目中的方法使用了最新的结果和多项式创造力的方法。