0
$\begingroup$

I hear of randomized reduction, deterministic reduction and non-deterministic reduction of complexity from A to B problems. This could make things impossible for polynomial time adversary prying into NP - hard problems.

Are these biases in complexity what makes the computation infeasible if a problem cannot be solved in polynomial time?

Does it matter really, whether a problem' solution is bounded and affirmed in a deterministic turing machine or non-deterministic turing machine?

Is it not plausible that to achieve the right cryptosystem to serve us another 100 years a vital consideration must be giving to a mix of all these reduction in polynomial time within a scope or formation of naturally existing context. e.g lattice or their matrix images?

FYI Please think about quantum resistant possibilities as you answer these questions. A good crypto scheme will give rise to a data stream that will bear no information but a verifier could still validate a prover without knowing much of the secret there in.

[AJI04] Miklos Ajtai. Generating hard instances of lattice problems. Quaderni di Matematica, 13:1–32,2004. Preliminary version in STOC 1996. – Jossy J. Umezurike 2 mins ago

[AKS] M. Ajtai, R. Kumar, and D. Sivakumar,A Sieve Algorithm for the Shortest Vector Problem, Proc.33rd Symp. Theory of Computing (STOC), pp. 601–610, 2001 https://github.com/jumezurike/backend-master-lokdonSKI/blob/master/README.md https://www.cs.uml.edu/~wang/acc-forum/avg/avgnp/node29.html

http://www.cs.toronto.edu/~sacook/homepage/1971.pdf

$\endgroup$
  • $\begingroup$ [AJI04] Miklos Ajtai. Generating hard instances of lattice problems. Quaderni di Matematica, 13:1–32,2004. Preliminary version in STOC 1996. $\endgroup$ – Jossy J. Umezurike Sep 20 at 12:57
  • $\begingroup$ [AKS] M. Ajtai, R. Kumar, and D. Sivakumar,A Sieve Algorithm for the Shortest Vector Problem, Proc.33rd Symp. Theory of Computing (STOC), pp. 601–610, 2001 cs.uml.edu/~wang/acc-forum/avg/avgnp/node29.html $\endgroup$ – Jossy J. Umezurike Sep 20 at 12:59
  • $\begingroup$ cs.toronto.edu/~sacook/homepage/1971.pdf $\endgroup$ – Jossy J. Umezurike Sep 20 at 13:00
  • $\begingroup$ I strongly believe that it depends on how you look at it. These are tautology. $\endgroup$ – Jossy J. Umezurike Sep 20 at 21:04
  • $\begingroup$ 3. Since P is usually an element of NP. We are not certain of NP being in P. unless some problem X can be reduced to NP: There is a fitting problem of NP hard caliber that could be reduced to NP complete problem. $\endgroup$ – Jossy J. Umezurike Sep 20 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.