There is a known formula for minimum number of states for such a finite automaton. This depends on $n$ as well as the radix $R$ of the underlying positional representation. If $n$ is coprime to $R$, ...

Take an $n$-state Turing machine $M$ which outputs $k$ one symbols. Define the new Turing machine $M'$ with $n+1$ states as follows. Every transition in $M$ to the ACCEPT state instead goes into a ...

Suppose you have a circuit which takes as input an advice string and a random string. (So this circuit would be in $BPP/Poly$ or something like that.) You can convert this into a purely deterministic ...

The probability of error when sampling $f(x)$ is $\delta$ when $x$ is chosen at random. Using self-correction, the probability of error is $2δ$ for all $x$ (not only random $x$)

You are looking at this the wrong way. Almost any object can be encoded into a natural number, so it would be possible to have a programming language with a single type. But the goal is to have more ...

I am a PhD graduate student in applied math who faced this exact problem last year. At my university, the applied math track offered much more flexibility in terms of course requirements. The CS track ...

Another typical case of $NPI$ problem is when there is a witness of length $\omega(\log n)$ but smaller than $n^{O(1)}$. The problem of the existence of a clique of size $\log n$ in a graph is a ...

Consider the following machine model. The machine with code $i$, upon input $x$, outputs $0$ always. Note that any machine $M$ in this model is universal, as $M(\langle \ulcorner M' \urcorner, x \... View answer 6 votes See the paper "A parallel approximation algorithm for positive linear programming." by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time. View answer 6 votes Kolmogorov complexity might fall into this category. One can show that there are certain strings, which cannot be compressed by any Turing machine. These strings behave "generically" so you can study ... View answer 5 votes I am surprised no one has mentioned primitive recursion. By restricting to bounded loops (i.e. the number of iterations for each loop must be calculated before the loop commences) the resulting ... View answer Accepted answer 5 votes To follow up on Snowie's post: For each term max(v1, v2) introduce a new variable$x_i$, subject to the constraints$x_i \geq v_1, x \geq v_2$For each term min(v1,v2) introduce a variable$y_i$... View answer 4 votes Suppose you are given input$w = \langle M, x, t \rangle$and are asked to decide if RAM machine$M$terminates on input$x$after$t$steps. By the time hierarchy theorem, the optimal algorithm to ... View answer 4 votes I am PhD student also interested in studying theoretical computer science, not really interested in other areas of CS. The route I took was to enter a PhD program in Applied Mathematics. (Pure ... View answer 4 votes The posting on MathOverflow tells how to go from a small number of independent Uniform[0,1] random variables to a larger number of pairwise-independent Uniform[0,1] random variables. You can of course ... View answer 4 votes Dealing with problems with continuous variables is very annoying with exact algorithms. For example, what does it mean to specify the edge-weights of a TSP instance with exact real numbers? When we ... View answer 4 votes The typical approach is to analyze the expected value of the running times of the algorithm. In this case, the expected value of the running time, on any problem with$m,n$, is something like$k^2$... View answer 4 votes The definitions of efficient reducibility are motivated in part by an analogy with recursion theory. In recursion theory, the m-reductions are closely connected to the arithmetical hierarchy. (m-... View answer 3 votes The following algorithms works well if the underlying field has a very small order$s$. Suppose we know$q$is irreducible, of a fixed degree$d$. Then, mod$q$, we know$x^{s^d} = x$holds. Hence it ... View answer Accepted answer 3 votes See https://mathoverflow.net/questions/58060/can-randomness-add-computability View answer 3 votes I would like to add to Dave Clarke's answer. The binary relations are sufficient to express higher-arity relations and functions (by adding new non-logical symbols if necessary). Hence, if you allow ... View answer 2 votes Let$H$be some complex hash function (almost any function will do), mapping long bit strings down to a single bit. Then to decide whether$H( A \times B ) = 0$, you will basically need to multiply$A ...

If the graph is a clique (or a set of disconnected cliques), then Luby's algorithm succeeds on the first iteration.

Testing whether two circuits of size $\leq N$ circuits are equivalent. To determine if $C_1 \sim C_2$ you only need to evaluate at the $2^n$ input points. To determine a class representative, one ...

The set of transcendentals is not open in $\mathbf R$ (in particular, it is dense and codense in $\mathbf R$. Hence it is undecidable.

Let $T$ be any recursively axiomatized but undecidable theory (such as arithmetic, set theory, etc.) Then the logical consequences of $T$ are recursively enumerable but not recursive.

To maximize the expression, given $x_i$, should set $y_i = m$ for the value of $i$ maximizing $x_i - \alpha$. This implies you should set $x_2, \dots, x_n = \alpha$ and $x_1 = 1 - (n-1) \alpha$. (I ...

Shortest path costs $O(E)$ using breadth-first search The best algorithms for max-flow are something like $O(EV)$ (plus some logarithmic factors). So I do not know in what sense they are equivalent (...