Question

Write a report Approximately 1000 word report (800-1300 words excluding Conclusion) on ONE of the following topics:

1. Quantum Cryptography

2. Quantum Computing and its impact on Cryptography

3. Zero-knowledge protocols (or proofs) in Signature Schemes

4. Secret Sharing (or splitting) in Cryptography

5. P vs. NP

It is VERY important that references are included (Note: Wikipedia is NOT acceptable)

Written Report for required format and marking criteria.

Note: Diagrams and / or images should be included. Any words associated with the diagrams should not be used in the 1000 word count for your report. (e.g. Diagram titles).

Answer 1

P vs. NP

Since the invention of the computer systems, a major part of the research is actually carried out in the field of computabiltiy theory and the complexity theory in order to understand what kind of problems can be solved using a computer system and which cannot. It is also a very interesting question among scientists to figure out if a problem is solvable or computable by a computer system then how much time would it take over the computer system to get solved. So the theory of computation or the whole computer science field actually revolve around these two theories.

Now, talking about the P and NP problems, the problems that can be found to be solved in a polynomial time are referred to as the P problems while the problems that cannot be solved in a polynomial time or the problems that can only be checked in a polynomial time are known as non-deterministic polynomial or NP problems. So when someone tries to say that P = NP then they are actually trying to find out if it is possible to solve the problems in polynomial time that can be verified in polynomial time. If P is not equal to NP then it means that there are problems that actually belong to the NP class that actually harder to compute than to verify in polynomial time.

It is one of the open problems in the field of Computer Science and it is one of those Millenium problems for which there is an award of US$1,000,000 to the person who can actually solve this problem. It was framed by Stephen Cook and Leonid Levin in 1970s. One of the most famous examples of such kinds of problems is of the sudoku in which if a player is playing the game in which the player is actually given a partially filled-in grid of numbers and attempts to fill the grid in accordance with the certain rules. Now, for an incomplete Sudoku grid, irrespective of nay size, does there exist any legal solution. In this case, any proposed solution can be easily verified, and the time to verify a solution grows slowly (polynomially) with the size of the grid. Therefore, the Sudoku is in NP (No-deterministic Polynomial time or quickly checkable) and it does not seem to be in P (Polynomial time or quickly solvable) problem.

Here's the solution to your question, please provide it a 100% rating. Thanks for asking and happy learning!!