>И с чего начать доказывать вообще что P != NP
Наверное в случае тебя с математики 1-го класса школы, потом второго и т.д.?
Не начинать. Ты видать не встречался с концепцией "галактических алгоритмов" раз так вольно рассуждаешь о сложности.
Если у тебя нет высшего математического, то даже и не думай.
Когда будет, ты сам поймёшь, почему тебе не стоит за это браться.
Пусть есть пароль pass, и его хэш Hash = hash(pass).
Задача P: проверить Hash известного пароля pass.
Эта задача решается быстро, за полиномиальное время, алгоритмом хэширования и сравнением.
Задача NP: найти неизвестный пароль pass, соответствующий известному хэшу Hash.
Эта задача решается медленно, за экспоненциальное время - алгоритмом прямого перебора всех возможных значений pass.
Но эту же задачу можно решить гораздо быстрее, за полиномиальное время, например вычислив местоположение владельца пароля и спиздив его у него, или местоположение хэша и подменив его там. Таким образом, задача переходит из класса NP в класс P, так как для неё существует более быстрый алгоритм решения её, за полиномиальное время.