# Theory of Computation: Question Set – 28

#### What is the difference between the P, NP, and NP-complete complexity classes?

The P complexity class consists of problems that can be solved in polynomial time by a deterministic Turing machine. The NP complexity class consists of problems that can be solved in polynomial time by a non-deterministic Turing machine, or verified in polynomial time by a deterministic Turing machine. The NP-complete complexity class consists of the hardest problems in NP, which are also believed to be the hardest problems in all of NP.

#### What is the difference between an oracle machine and a standard Turing machine?

An oracle machine is a theoretical model of a Turing machine that has access to an oracle, which is a black box that can solve a certain problem in constant time. This allows the machine to solve certain problems much more quickly than a standard Turing machine, which can only solve problems by performing individual steps.

#### What is the difference between a reduction and a complete problem?

A reduction is a technique used in the theory of computation to show that one problem can be transformed into another problem in a certain way. A complete problem is a problem that is as hard as the hardest problems in a certain complexity class, in the sense that any problem in the class can be reduced to it in polynomial time.

#### What is the difference between the halting problem and Rice’s theorem?

The halting problem is the problem of determining whether a program will halt or run forever on a given input. Rice’s theorem states that any non-trivial property of the behavior of a program is undecidable, which means that there is no algorithmic solution to many important problems in program analysis and verification.

#### What is the difference between a one-way function and a trapdoor function?

A one-way function is a function that is easy to compute in one direction but hard to invert in the other direction, without knowledge of a secret key. A trapdoor function is a one-way function that also has a secret trapdoor that allows it to be easily inverted by someone who has the key.

#### What is the difference between a cryptographic hash function and a symmetric-key encryption algorithm?

A cryptographic hash function is a one-way function that maps an input of arbitrary size to a fixed-size

#### What is the difference between a Turing machine and a finite automaton?

A Turing machine is a theoretical model of a computer that can read and write to an infinite tape, while a finite automaton is a theoretical model of a computer that has a fixed number of states and transitions based on input. Turing machines are more powerful than finite automata, as they can simulate any algorithm that can be executed by a computer.

#### What is the Church-Turing thesis?

The Church-Turing thesis is a hypothesis that states that any algorithmic problem that can be solved by a computer can be solved by a Turing machine. This hypothesis has not been formally proven, but is widely accepted as true by computer scientists.