P versus UP (P versus UP)

Frank Vega (vega.frank@gmail.com)

This paper appears in: Revista IEEE América Latina

Publication Date: June 2012
Volume: 10,   Issue: 4 
ISSN: 1548-0992

The existence of one-way functions is a question that has not yet been answered. If we solve the problem P versus UP showing that both classes are different, then it would result in fact there are strong one-way functions and thus P is not equal to NP. In this work we showed that some kinds of unambiguous Turing machines can not be converted into deterministic, because it will imply that some Turing machines which do not halt for some inputs could be decided in polynomial time by certain deterministic Turing machines. But, is impossible that we can decide in polynomial time over a deterministic Turing machine if any deterministic Turing machine does not halt in polynomial time. Therefore by the rule of reduction ad absurdum we have that P and UP are different.

Index Terms:
Complexity classes,Turing machines,One-way functions   

Documents that cite this document
This function is not implemented yet.

[PDF Full-Text (259)]