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.