Skip to main content
fixed spelling
Source Link

Complexity theory has a another notion of one-way functions: worst-case one-way functions.

It is known that $P \ne NP$ if and only if worst-case one-way functions exist.

Worst-case one-way functions existsexist if and only if there is injective length-increasing polynomial-time computable function that iscan not invertiblebe inverted in polynomial-time.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

Complexity theory has a another notion of one-way functions: worst-case one-way functions.

It is known that $P \ne NP$ if and only if worst-case one-way functions exist.

Worst-case one-way functions exists if and only if there is injective length-increasing polynomial-time computable function that is not invertible in polynomial-time.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

Complexity theory has a another notion of one-way functions: worst-case one-way functions.

It is known that $P \ne NP$ if and only if worst-case one-way functions exist.

Worst-case one-way functions exist if and only if there is injective length-increasing polynomial-time computable function that can not be inverted in polynomial-time.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.

Source Link

Complexity theory has a another notion of one-way functions: worst-case one-way functions.

It is known that $P \ne NP$ if and only if worst-case one-way functions exist.

Worst-case one-way functions exists if and only if there is injective length-increasing polynomial-time computable function that is not invertible in polynomial-time.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.