# Tag Info

419

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 ...

208

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{NP}$). As ...

149

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,...

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$] ...

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 ...

48

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 ...

32

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 ...

32

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

More than useful mentioned answers, I recommend you highly to watch "Beyond Computation: The P vs NP Problem" by Michael Sipser. I think this video should be archived as one of the leading teaching video in computer science.! Enjoy!

26

Consider the following algorithm (or procedure, or piece of code, or whatever): Contrive(n) 1. if n = 0 then do something Theta(n^3) 2. else if n is even then 3. flip a coin 4. if heads, do something Theta(n) 5. else if tails, do something Theta(n^2) 6. else if n is odd then 7. flip a coin 8. if heads, do something Theta(n^4) 9. else if ...

22

Grammars are inherently recursive objects, so the answer seems obvious: by induction. That said, the specifics are often tricky to get right. In the sequel I will describe a technique that allows to reduce many a grammar-correctness proof to mechanical steps, provided some creative preprocessing is done. $\newcommand{\lang}{\mathcal{L}(#1)} \newcommand{\... 19 The Special Case Assume we want to show$L_1 \leq_R L_2$with respect to some notion of reduction$R$. If$L_1$is a special case of$L_2$, that is quite trivial: we can essentially use the identity function. The intuition behind this is clear: the general case is at least as hard as the special case. In "practice", we are given$L_2$and are stuck with ... 17 Skiena provides a sorted list of the dominance relations between the most common functions in his book, The Algorithm Design Manual: $$n!\gg c^n \gg n^3 \gg n^2 \gg n^{1+\epsilon} \gg n \lg n \gg n \gg n^{1/2}$$ $$\gg \lg^2n \gg \lg n \gg \frac{\lg n}{\lg\lg n} \gg \lg\lg n \gg \alpha(n) \gg 1$$ Here$\alpha(n)$denotes the inverse Ackermann function. 15 It doesn't just "know", it checks every time. Basically, it does the same thing you would do: in order to compare, it checks (from the left) which number has the first digit that is larger than the corresponding one in the other number. Of course you have to add leading zeroes to the shorter number. Letters are just numbers for the computer. Humans have ... 15 The Akra-Bazzi method The Akra-Bazzi method gives asymptotics for recurrences of the form: $$T(x) = \sum_{1 \le i \le k} a_i T(b_i x + h_i(x)) + g(x) \quad \text{for x \ge x_0}$$ This covers the usual divide-and-conquer recurrences, but also cases in which the division is unequal. The "fudge terms"$h_i(x)$can cater for divisions that don't come out ... 15 Leveraging a known nearby problem When faced with a problem that feels hard, it is often a good idea to try to search for a similar problem that is already proven hard. Or, perhaps you can immediately see that a problem is very similar to a known problem. Example problem Consider a problem $$\text{DOUBLE-SAT} = \{ \varphi \mid \varphi \text{ is a ... 14 A practical approach that in many examples works [but not always, I know] is trying to find the nesting structure of the strings in the language. "Nested dependencies" have to be generated at the same time in different parts of the string. Also we have the basic toolbox: concatenation: S\to S_1S_2 if you can split the language in two consecutive ... 13 A stronger version of the Ogden's condition (OC) is the Bader-Moura’s condition (BMC) A language L\subseteq \Sigma^* satisfies BMC if there exists a constant n such that if z \in L and we label in it "distinguished" positions d(z) and e(z) "excluded" positions, with d(z) > n^{e(z)+1}, then we may write z = uvwxy such ... 13 Other answers have addressed this from a more theoretical perspective. Here is a more practical approach. For "typical" NP-complete decision problems ("does there exist a thingy that satisfies all these constraints?"), this is what I would always try first: Write a simple program that encodes your problem instance as a SAT instance. Then take a good SAT ... 13 One useful tool is Rice's theorem. Here is what it says: Let \emptyset \subsetneq P \subsetneq \mathcal{P} a non-trivial set of partially computable unary functions and \varphi a Gödel numbering of \mathcal{P}. Then the index set of P \qquad I_P = \{ i \in \mathbb{N} \mid \varphi_i \in P \} is not recursive. You find it also ... 13 Excellent question! Nondeterminism first appears (so it seems) in a classical paper of Rabin and Scott, Finite automata and their decision problems, in which the authors first describe finite automata as a better abstract model for digital computers than Turing machines, and then define several extensions of the basic model, including nondeterministic finite ... 12 Summations Often one encounters a recurrence of the form$$ T(n) = T(n-1) + f(n), $$where f(n) is monotone. In this case, we can expand$$ T(n) = T(c) + \sum_{m=c+1}^n f(m), $$and so given a starting value T(c), in order to estimate T(n) we need to estimate the sum f(c+1) + \cdots + f(m). Non-decreasing f(n) When f(n) is monotone non-... 11 Elementary methods Finite automata (possibly nondeterministic, with empty transitions). Regular expressions. Right (or Left, but not both) linear equations, like X = KX + L where K and L are regular. Regular (Type 3) grammar. Operations preserving regular languages (Boolean operations, product, star, shuffle, morphisms, inverses of morphisms, reversal,... 11 Copying my answer to a similar question on Stack Overflow: The easiest way to explain P v. NP and such without getting into technicalities is to compare "word problems" with "multiple choice problems". When you are trying to solve a "word problem" you have to find the solution from scratch. When you are trying to solve a "multiple choice problems" you have ... 11 There is one characterisation of CFL that can be of use, the Chomsky-Schützenberger theorem. Dyck language Let T an alphabet. We define the Dyck-language D_T \subseteq (T \cup \hat{T})^* of T by the context-free grammar G = (\{S\}, T \cup \hat{T}, \delta, S) with \delta given by \qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad ... 10 Algorithm analysis, like theorem proving, is largely an art (e.g. there are simple programs (like Collatz problem) that we do not know how to analyze). We can convert an algorithm complexity problem to a mathematical one, as answered comprehensively by Raphael, but then in order to express a bound on the cost of an algorithm in terms of known functions, we'... 9 It's not the operating system that compares integers, the CPU is taking care of it. It's made on logical gates level, please refer to these slides to see how it can be done. About the alphabet, in ASCII alphanumeric and other special characters are represented as integers so comparing them is also an integer comparison operation, which is performed by the ... 9 There may be times when you come across a strange recurrence like this:$$T(n) = \begin{cases} c & n < 7\\ 2T\left(\frac{n}{5}\right) + 4T\left(\frac{n}{7}\right) + cn & n\geq 7 \end{cases}$\$ If you're like me, you'll realize you can't use the Master Theorem and then you may think, "hmmm... maybe a recurrence tree analysis could work." Then ...

9

Simplest of them is P, problems solvable in polynomial time belongs here. Then comes NP. Problems solvable in polynomial time on a non-deterministic Turing machine belongs here. The hardness and completeness has to with reductions. A problem A is hard for a class C if every problem in C reduces to A. If problem A is hard for NP, or NP-hard, if every ...

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