David Harris
  • Member for 10 years, 7 months
  • Last seen this week
Finite automata that accept binary strings divisible by n
Accepted answer
32 votes

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

View answer
Is every busy beaver strictly monotonic asymptotically?
Accepted answer
16 votes

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

View answer
Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?
Accepted answer
11 votes

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

View answer
On the need for a self-correcting function in the PCP theorem
Accepted answer
10 votes

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$)

View answer
Boolean as subtype of integer
10 votes

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

View answer
Graduate studies (PhD) in CS Theory vs. Applied Math
10 votes

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

View answer
Why are NPI problems not all of the same complexity?
9 votes

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

View answer
If an abstract machine can simulate itself, does that make it Turing complete?
9 votes

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
Complexity of linear programming
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
Using negative results to prove positive results in computability theory
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
Programming languages for efficient computation
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
Solving a Min/Max equation set
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
What are some problems where we know we have an optimal algorithm?
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
Advice for Graduate School in Computer Science
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
Pairwise independent gaussians
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
Theoretical Applications for Approximation Algorithms
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
How to analyze a randomized recursive algorithm?
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
Many-one reductions vs. Turing reductions to define NPC
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
Find the remainder of a large fixed polynomial when divided by a small unknown polynomial
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
Is a turing machine with random number generator more powerful?
Accepted answer
3 votes

See https://mathoverflow.net/questions/58060/can-randomness-add-computability

View answer
Any Graph is a Model (! or ?)
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
Decision version of matrix multiplication problem
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 ...

View answer
Maximum Independent Set using Maximal MIS
2 votes

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

View answer
Example where equivalence is easy but finding class representative is hard
2 votes

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

View answer
Decidability of transcendental numbers
1 votes

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

View answer
Recursively enumerable, non-recursive language without using Gödel's number
1 votes

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.

View answer
Upper bound of an optimization problem
1 votes

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

View answer
shortest path & max flow
1 votes

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

View answer
is "spaghetti sort" really O(n) (even as a thought experiment) ?
0 votes

The key sticking point is that analysis of algorithms is about the evolution of abstract machines with respect to data. It does NOT apply to the evolution of physical systems. In the latter case, ...

View answer
Learning with "taciturn" oracles
0 votes

It appears that only finitely many valid passwords can in fact be used. If the password language is finite, then there is no hope (as in this case, all of the valid passwords may be used, in which ...

View answer