# Tag Info

## Hot answers tagged computer-science

28

This is a known property of the Leibniz–Gregory series, and has been used to actually compute $\pi$ to many digits using this series. It arises from the Euler–Maclaurin formula: $$\frac{\pi}{2} - 2 \sum_{k=1}^\frac{N}{2} \frac{(-1)^{k-1}}{2k-1} \sim \sum_{m=0}^\infty \frac{E_{2m}}{N^{2m+1}}$$ where $E_n$ are the Euler numbers. When $N$ (the number of terms) ...

25

Determining for any statement if there is a proof with $n$ symbols or less is an $NP$ problem (i.e. the proof can be checked in polynomial time with respect to the length of the proof and the statement), that's probably the sense in which they meant that "P versus NP is itself NP". However, it does not really make sense to assign a complexity class ...

18

The "P versus NP" problem is a single yes-no question: is $NP = P$? The correct answer is either "yes" or "no", we just don't know which. But the complexity of the answer is $1$.

12

We have a signature $S$ and we extend it to $S':=S\cup\{P\}$. The $S$-definition of $P$ is the $S'$-formula $$\forall v_0\dots v_{n-1}: Pv_0\dots v_{n-1}\leftrightarrow \phi_P(v_0,\dots,v_{n-1})$$ which can be formally handled as an extra axiom to the given $S$-theory we're working with, thus producing an equivalent $S'$-theory, in which the symbol $P$ can ...

12

Below I'll first try to describe the process in a more intuitive way, then address your worries about circularity. I suspect the latter point may actually be more helpful, so feel free to read the second section first - and in particular, the highlighted motto there will I think be quite helpful. (Re: your final comment, the definition is $(1)$ - the thing ...

9

The cycle starts and ends in the same vertex, but the path does not.

9

To avoid catastrophic cancellation occurring when $x \to 0$, then as Raymond Manzoni's question comment suggests, rationalize $1 - \sqrt{1 - x^2}$ to get \begin{equation}\begin{aligned} 1 - \sqrt{1 - x^2} & = (1 - \sqrt{1 - x^2})\left(\frac{1 + \sqrt{1 - x^2}}{1 + \sqrt{1 - x^2}}\right) \\ & = \frac{1 - (1 - x^2)}{1 + \sqrt{1 - x^2}} \\ & = \... 7 Model theory and logic aren't separated; model theory is a subfield of logic, the other three main subfields being proof theory, set theory, and computability theory. Keep in mind that taxonomies and delineations of mathematical subfields are entirely sociological, so there's a lot of subjectivity here. The slogan "model theory is semantics and proof ... 7 Since by definition T(n)= n+ \sum_{k=1}^{n-1} (T(n-k)+T(k)) = n + 2\sum_{k=1}^{n-1} T(k) $$you can rewrite, for any n, that$$ T(n+1)= n + 1 + 2\sum_{k=1}^{n} T(k) = 1+ 2T(n)+ \underbrace{n+ 2\sum_{k=1}^{n-1} T(k)}_{T(n)} = 1+3T(n) $$This is easily solved: T(1)=1 and T(n+1)=3T(n)+1 have the solution$$ \boxed{\forall n\geq 1,\qquad T(n) = \frac{1}{...

6

In order for the $k$ entry to be counted in $c_{ij}$, we must have $1\le i\le k$ and $k\le j\le n$. There are $k$ integers in the set $\{1,2,\ldots,k\}$ and $n-(k-1)=n+1-k$ integers in the set $\{k,k+1,\ldots,n\}$, so there are $k(n+1-k)$ pairs $\langle i,j\rangle$ such that the $k$ entry is counted in $c_{ij}$. It contributes $k$ to each of those sums $c_{... 5 When settling for$p, p', p'', \ldots$as propositoinal variables, sticking to prefix notation and restricting oneself to a fixed set of operators, the language of propositional logic can be given as a context-free grammar:$\langle \{F, P, U, B\}, \{\neg, \land, \lor, \to, p, ', "(", ")", ","\}, R, F \rangle$, where$R =\{ F \longrightarrow P\\ F \...

5

This is an example of a Galois connection, which is a relationship between two partially ordered sets. It's a special case of the concept of adjunction in category theory. In particular, let $\mathscr S$ be a thin category (i.e. a preorder) whose object set is $S_1 + S_2$, such that $\mathscr S(s, s')$ is inhabited iff $s R_1 s'$. Likewise, let $\mathscr T$ ...

5

(Not too) Short answer. Yes, the rules $(Assm)$ and $(\equiv)$ are axioms. By axiom here (and in many textbooks such as Takeuti's Proof Theory cited by MauroALLEGRANZA) is intended an inference rule with no premises. In this sense, every proof system needs at least an axiom rule, otherwise there is no possibility to build a derivation: without any axiom, ...

5

Since the hash function is uniform, to find $P(z \geq c \log n)$ we can simply count the number of elements in $S = \{1,\ldots,n\}$ that satisfy $z \geq c \log n$. Take $n=2^p$ for some $p\in\mathbb{N}$. Then $n/2$ elements in $S$ end on one zero, $n/4$ elements end on two zeros, etc. So, $P(z \geq c \log n) = (n/2)/n = 1/2$ for $c\log n =1$, $1/4$ for $c\... 5 We know that the probability that it incorrectly answers "yes" on some composite in$n$trials of the algorithm is$\left(\frac14\right)^n$so the probability that it answers "no" at least once in$n$runs is$1-\left(\frac14\right)^n$. Thus, we want to find$n$such that $$1-\left(\frac14\right)^n\geq1-\frac1k$$ or $$\frac1k\geq\left(\... 5 Each row in the array below represents a set of terms in one of the sums. So n=4 in this example, and the first row contains the term of c_{11}, the second row the terms of c_{12}, and so on until the last row which contains the term of c_{44}.$$ \begin{array}{ccccc} a_1\\ a_1 & a_2\\ a_1 & a_2 & a_3\\ a_1 & a_2 & a_3 & a_4\\ ... 5 No, the degree sequence is not a function on$V(G)$, although it involves a function on$V(G)$indirectly in its definition, namely the function$d : V(G) \to \{0,1,2,3,...\}$which assigns to each$v \in V(G)$its degree$d(v)$. Amongst all enumerations of the vertex set$V_G$, choose an enumeration$v_1,v_2,...,v_n$of$V_G$having the property that $$d(... 5 For error-correcting codes, the geometry is really the natural thing for which to ask. That is, we want code words to be sufficiently far apart, so that we can easily detect and correct errors. In order to measure distance, we have some sort of metric. This metric induces a geometry on the space. Now if we want to compute things, it is often helpful to have ... 5 There's no difference. Lambda Calculus can't tell if you write \lambda x . M, if you write f(x) = M or if you write \hat{x} . M (which apparently was church's original notation? I haven't fact checked that, though). The reason people care about lambda calculus is because it has exactly 3 combinatorial rules from which all computation follows. The dream ... 4 It means that the left side is bounded by a constant C_{d} > 0 times the right side, and the constant C_{d} depends only on the number d and nothing else. Sometimes this is written instead with "big O" notation x= O_{d}(y) (or, equivalently, x\leq O_{d}(y)). ** Added later by request: A source for this notation is the wikipedia article:... 4 Assume that x_i<x for every i. Then:$$x=\frac{x_1+...+x_n}{n}<\frac{x+...+x}{n}=\frac{nx}{n}=x $$Which is a contradiction 4 As Henno Brandsma commented, soundness is a measure of health of the system (does it do anything we would not want it to?), and completeness is a measure of usefullness (could it do anything we may want it to?). Basically: Sound: Anything we might get is something we would want. Nothing bad can happen. Complete: Anything we might want is something we ... 4 To make this question most significant, we want to work with a notion of "logical system" more-or-less along the following lines: a tuple (Sent, \models, \vdash) where \models is a relation between structures and sentences, \vdash is a relation between sets of sentences and sentences, and \models and \vdash need not be connected by a ... 4 Is \models called (logical) consequence relation between formulas? Yes. Or (logical) inference or (logical) entailment or semantic consequence/inference/entailment. Is \unicode{x27DA} called (logical) equivalence relation between formulas? Yes. Is \vdash called derivable relation between formulas? It is called derivability. Is \unicode{... 4 I'm assuming it's program P that is only allowed to use a finite amount of memory. Yes, this is computable. Simulate program P and record all the intermediate states that program P passes through; there are at most 2^{2^n} of them. Eventually, either P terminates, or it will reach a state that it has been in before; in that case, P will never ... 4 One must be careful, there is a crucial difference between$$(\log n)^{\log n}$$and$$\log n^{\log n}$$The exponent rule for the logarithm can be applied to this last one to obtain:$$\log n^{\log n}= \log n \log n=(\log n)^2 \neq (\log n)^{\log n}$$4 The numbers you’ve labelled as c_i are the binomial coefficients \binom ni; the code checks whether \binom ni \equiv 0 \pmod n for all 0 < i \le \frac n2. This is not the AKS algorithm. It’s the exponential-time brute force algorithm listed in the Wikipedia article to motivate the AKS algorithm. 4 If we take \log_2 of everything, we end up with a simpler game that is equivalent to the original (\log is monotonically increasing, so x>n iff \log x > \log n). I will denote \log_2x by y and \log_2n by m. When we take the log, squaring becomes doubling, and cubing becomes tripling. Then this game is equivalent to the following: Start ... 4 When you multiply two matrices, \mathbf{A} with r rows and n columns, and \mathbf{B} with n rows and c columns, the result is matrix \mathbf{C} with r rows and c columns, via$$C_{i j} = \sum_{k=1}^{n} A_{i k} B_{k j} \quad \text{ for } \quad i = 1 \dots r, \quad j = 1 \dots c$$which involves$r n c\$ scalar multiplications. When you ...

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