Understanding the basics – Computational Complexity
In Computational Complexity, one of the most important but misconceived facts is, understanding the Difference of Problem, Algorithm, and Language. In this App Atlantis Blog on Computational Complexity, you can understand this difference very simply.
For simplicity, We will begin by solely considering “decision” issues, that have a yes/no answer. Function problem works roughly the same method, except in lieu of yes/no, there’s a specific output word related to every input word.
Understanding Language – Computational Complexity
Language: In Computational Complexity a language is just a collection of strings. If you have an alphabet, such as Σ, then Σ∗ is the set of all words containing only the symbols in Σ. For example, ∗ it is the set of all binary sequences of any length. An alphabet doesn’t need to be binary, though. It can be unary, ternary, etc.
A language over an alphabet Σ is any set of Σ∗.
Understanding Problem – Computational Complexity
Problem: According to Computational Complexity, a problem is a few questions regarding some input we’d like answered. Specifically, a decision problem is a question which asks, “Does our given input fulfill property X?
A language is that the formal realization of a problem. When we wish to reason in theory about a decision problem, we often examine the corresponding language. For problem X, the corresponding language is: L=
Determining if the solution for input to a choice problem is “yes” is similar to deciding whether or not the encryption of that input over an alphabet is within the corresponding language.
Understanding Algorithm – Computational Complexity
Algorithm: In “Computational Complexity”, an algorithmic rule is a stepwise way to solve a problem. Note that there an algorithmic rule that is possible to express in a lot of ways and plenty of languages and that there are many alternative algorithms resolving any given problem.
Algorithm With Turing Machine
Turing machine is one of the good topics to understand the algorithm. And in “Computational Complexity” Turing Machine is very important as well.
Turing Machine: A Turing machine is the formal analog of an algorithmic rule. A “Turing Machine” over a given alphabet, for every word, either can or will not halt in an acceptive state. Thus for every Turing machine M, there is a corresponding language:
(There’s a subtle difference between Turing Machines that halt on all inputs and halt on yes inputs, which defines the difference between complexity classes R and RE.)
The relationship between languages and Turing Machines is as follows
1. Every Turing Machine accepts exactly one language
2. There may be more than one Turing Machine that accepts a given language
3. There may be no “Turing Machine” that accepts a given language.
We can say roughly an equivalent factor regarding algorithmic rules and problems: each algorithm solves one problem, but there may be, or many, algorithms solving a given problem.
Comparing Problem And Algorithm By Time Complexity
Time Complexity: one amongst the most common sources of confusion between algorithms and problems is in regards to complexness categories. The correct allocation can be summarized as follows:
• An algorithm has a “time complexity”
• A problem belongs to a complexity class
An algorithm can have a certain time complexity. We say an algorithmic rule contains a worst-case upper-bounded complexness f(n) if the algorithmic rule halts in at the most f(n) steps for any input of size n.
Problems don’t have run-times since a problem isn’t tied to a specific algorithm that actually runs. Instead, we say that a problem belongs to a complexness category if there exists some algorithmic rule resolution that problem with a given time complexness.
P, NP, PSPACE, EXPTIME, etc. are all complexity classes. This means they contain problems, not algorithms. An algorithm can never be in P, but if there’s a polynomial-time algorithm solving a given problem X, then X is in P. There could also be a bunch of exponential-time algorithms accepting X, but since there exists a single polynomial-time algorithm accepting X, it is in P.