* Warren Smith <warren.wds@gmail.com> [Feb 14. 2013 19:47]:
True, proving P unequal NP would be a needed first step to prove reverse is superpolynomially harder like cryptologists want.
So... let us lower our goals... Can we prove for some problem, that the forward computation is some polynomial, while the backward is some higher-degree polynomial (at least)?
Deliberatedly vague: Some function using (sub-)graph isomorphism. IIRC there are cryptosystems using graph problems that are provably NP-something. (Cannot even name the researcher(s) right now).
Or... can we even prove a logarithmic gap -- I already proved one, but only for parallel computing; I want now a gap for ordinary sequential compute time.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun