377

I think the Wikipedia articles $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good. Still here is what I would say: Part I, Part II [I will use remarks inside brackets to discuss some technical details which you can skip if you want.] Part I Decision Problems There are various kinds of computational problems. However in an ...


186

Part II Continued from Part I. The previous one exceeded the maximum number of letters allowed in an answer (30000) so I am breaking it in two. $\mathsf{NP}$-completeness: Universal $\mathsf{NP}$ Problems OK, so far we have discussed the class of efficiently solvable problems ($\mathsf{P}$) and the class of efficiently verifiable problems ($\mathsf{...


140

Translating Code to Mathematics Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements,...


96

There are several methods to do the conversion from finite automata to regular expressions. Here I will describe the one usually taught in school which is very visual. I believe it is the most used in practice. However, writing the algorithm is not such a good idea. State removal method This algorithm is about handling the graph of the automaton and is ...


77

I'd say the most well known barriers to solving $P=NP$ are Relativization (as mentioned by Ran G.) Natural Proofs - under certain cryptographic assumptions, Rudich and Razborov proved that we cannot prove $P\neq NP$ using a class of proofs called natural proofs. Algebrization - by Scott Aaronson and Avi Wigderson. They prove that proofs that algebrize ...


76

You are referring to the Landau notation. They are not different symbols for the same thing but have entirely different meanings. Which one is "preferable" depends entirely on the desired statement. $f \in \cal{O}(g)$ means that $f$ grows at most as fast as $g$, asymptotically and up to a constant factor; think of it as a $\leq$. $f \in o(g)$ is the ...


76

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM. The model is intended to reflect the behavior of real computers more accurately than the Turing machine model. Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (...


69

To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it's not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free. That said, I am also interested in other techniques than the ...


61

There are numerous containments known. Let $\subseteq$ denote containment and $\subset$ proper containment. Let $\times$ denote incomparability. Let $LL = \bigcup_k LL(k)$, $LR = \bigcup_k LR(k)$. Grammar level For LL $LL(0) \subset LL(1) \subset LL(2) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$ $SLL(1) = LL(1), ...


61

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular. The following properties can be used: The pumping lemma, as exemplified in Dave's answer; Closure properties of regular languages (set operations, concatenation, ...


57

Note: I haven't checked the answer carefully yet and there are missing parts to be written, consider it a first draft. This answer is meant mainly for people who are not researchers in complexity theory or related fields. If you are a complexity theorist and have read the answer please let me know if you notice any issue or have an idea about to improve the ...


57

Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist? [notational note: we can relate any function $f$ with a language $L_f=\{ (x,y) \mid y=f(x) \}$ and then discuss the decidability of $L_f$ rather than the computability of $f$] ...


54

There are a number of well-studied strategies; which is best in your application depends on circumstance. Improve worst case runtime Using problem-specific insight, you can often improve the naive algorithm. For instance, there are $O(c^n)$ algorithms for Vertex Cover with $c < 1.3$ [1]; this is a huge improvement over the naive $\Omega(2^n)$ and might ...


53

For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word. Language: a language is simply a set of strings. If you have an alphabet, such as $\Sigma$, then $\Sigma^*$ is the set of all ...


50

Method The nicest method I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods. Let $A= (Q,\Sigma,\delta,q_0,F)$ an NFA without $\varepsilon$-transitions. For every state $q_i$, create the equation $\qquad \...


48

Yes, if you can come up with any of the following: deterministic finite automaton (DFA), nondeterministic finite automaton (NFA), regular expression (regexp of formal languages) or regular grammar for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common. There are also useful properties outside of the ...


48

If you want rigorous proof, the following lemma is often useful resp. more handy than the definitions. If $c = \lim_{n\to\infty} \frac{f(n)}{g(n)}$ exists, then $c=0 \qquad \ \,\iff f \in o(g)$, $c \in (0,\infty) \iff f \in \Theta(g)$ and $c=\infty \quad \ \ \ \iff f \in \omega(g)$. With this, you should be able to order most of the ...


47

This is a broad question that does not have an easy answer; it's a long way from electrons skittering along copper wires to rendering a website in Firefox. I will attempt to give you an overview from bottom to top and point you towards the right things to look up. Encoding Numbers The basic motivation is to compute things, as in doing arithmetics¹. The ...


45

Ogden's Lemma Lemma (Ogden). Let $L$ be a context-free language. Then there is a constant $N$ such that for every $z\in L$ and any way of marking $N$ or more positions (symbols) of $z$ as "distinguished positions", then $z$ can be written as $z=uvwxy$, such that $vx$ has at least one distinguished position. $vwx$ has at most $N$ distinguished ...


43

Big O: upper bound “Big O” ($O$) is by far the most common one. When you analyse the complexity of an algorithm, most of the time, what matters is to have some upper bound on how fast the run time¹ grows when the size of the input grows. Basically we want to know that running the algorithm isn't going to take “too long”. We can't express this in actual time ...


39

Landau notation denotes asymptotic bounds on functions. See here for an explanation of the differences among $O$, $\Omega$ and $\Theta$. Worst-, best-, average or you-name-it-case time describe distinct runtime functions: one for the sequence of highest runtime of any given $n$, one for that of lowest, and so on.. Per se, the two have nothing to do with ...


37

Based on Dave's answer, here is a step-by-step "manual" for using the pumping lemma. Recall the pumping lemma (taken from Dave's answer, taken form Wikipedia): Let $L$ be a regular language. Then there exists an integer $n\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $n$ ($n$ is called the "pumping length") can be ...


35

Maybe the most common technique that cannot be used is relativization, that is, having a TM with oracle access. The impossibility follows from a paper by Theodore Baker, John Gill, Robert Solovay who show the existence of two oracles (languages), $A$ and $B$ such that $\text{P}^A = \text{NP}^A$ and $\text{P}^B \ne \text{NP}^B$. Thus, if some proof for, ...


35

Converting Full History to Limited History This is a first step in solving recurrences where the value at any integer depends on the values at all smaller integers. Consider, for example, the recurrence $$ T(n) = n + \frac{1}{n}\sum_{k=1}^n \big(T(k-1) + T(n-k)\big) $$ which arises in the analysis of randomized quicksort. (Here, $k$ is the rank of the ...


34

Closure Properties Once you have a small collection of non-context-free languages you can often use closure properties of $\mathrm{CFL}$ like this: Assume $L \in \mathrm{CFL}$. Then, by closure property X (together with Y), $L' \in \mathrm{CFL}$. This contradicts $L' \notin \mathrm{CFL}$ which we know to hold, therefore $L \notin \mathrm{CFL}$. This is ...


34

This part of computer science is called analysis of algorithms. Many times people are satisfied when they are given a guarantee that an algorithm’s performance is not worse than a specified bound and they dont’t care about the exact performance. This bound is conveniently denoted with the Landau-notation (or big-Oh notation) and in case of $\mathcal{O}(f(n))...


31

First your integer numbers are converted into binary numbers. For example, the integer 2 is converted to 0010. The CPU uses a digital comparator: A digital comparator or magnitude comparator is a hardware electronic device that takes two numbers as input in binary form and determines whether one number is greater than or less than or equal to the ...


31

Execution Counts of Statements There is another method, championed by Donald E. Knuth in his The Art of Computer Programming series. In contrast to translating the whole algorithm into one formula, it works independently from the code's semantics on the "putting things together" side and allows to go to a lower level only when necessary, starting from an "...


28

From Wikipedia, the pumping language for regular languages is the following: Let $L$ be a regular language. Then there exists an integer $p\ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = xyz$ (i.e., $w$ can be divided into three substrings), satisfying ...


28

Brzozowski algebraic method This is the same method as the one described in Raphael's answer, but from a point of view of a systematic algorithm, and then, indeed, the algorithm. It turns out to be easy and natural to implement once you know where to begin. Also it may be easier by hand if drawing all the automata is impractical for some reason. When ...


Only top voted, non community-wiki answers of a minimum length are eligible