Theory of Computation

Computational Theory Basics

The theory of computation focuses on means and methods to solve problems using more efficient algorthims. There serveral concentrations within the feild. Automa Theory, Computability Theory, and Computational Complexity Theory.

A decision problem is one where the output for any given input is either yes or no. For the problem to be considered decidable the inputs which return yes should be in the set of natural numbers.

Within computation problems are divided into several categories. Class P and Class NP are two of the many classes. Class P includes decidable problems which can be solved in a polynomial amount of time. Where class NP are problems which are not decidable problems and they are solved in much more time.

The P vs NP problem focuses on proving if the statement P = NP is a true statement. This is a key proof since P problems are solved within a polynomial amount of time, and NP problems takes lots of computational energy. If P = NP is a true statement then it allows for NP problems to be solved in a significantly less amount of time.

Sources: Decision Problem Computable Set P class and NP Class P VS NP

My name

Sarissa theme designed by iozcelik