One-Way Functions and 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.