The computation tag has no usage guidance.

**7**

votes

**2**answers

717 views

### Complexity of Turing Machine behavior

If one looks at the code for a Turing Machine (TM) with
$q$ states and, let's say, $2$ symbols, they all look
pretty much the same:
A list of $5$-tuples:
$$
< state, symbol{-}read, symbol{-}to{-}...

**18**

votes

**0**answers

374 views

### Checking Mertens and the like in less than linear time or less than $\sqrt{x}$ space

Say you want to check that $|\sum_{n\leq x} \mu(n)|\leq \sqrt{x}$ for all
$x\leq X$. (I am actually interested in checking that $\sum_{n\leq x} \mu(n)/n|\leq c/\sqrt{x}$, where $c$ is a constant, and ...

**4**

votes

**0**answers

67 views

### Efficiently computing all equivariant maps between two $GL_n$-representations

This is sort of a strange question; if it's not appropriate for MathOverflow I apologize in advance.
I'm in a situation where I'd like to be able to give a computer two $GL_n$ representations $V$ and ...

**1**

vote

**1**answer

170 views

### Polygonal Mersenne numbers [closed]

I posted the same question on Math SE since this one got put on hold.
Link to Math SE question:Polygonal Mersenne numbers
Polygonal numbers are of the form $\cfrac {n^2(s-2)-n(s-4)}{2}$, where $s$ ...

**-1**

votes

**1**answer

61 views

### How to generate computational data in graph theory?

For a given number of nodes how many non-isomorphic graphs are available? Might be this is an open problem. For less number of vertices some computational statistics available.
I want to get all non-...

**0**

votes

**0**answers

65 views

### Bits of precision matrix reconstruction

We have a real rank $r$ matrix $M\in\{0,1\}^{n\times n}$.
Suppose we have diagonalized using $LMR=D$.
I want to recover a real matrix $\widetilde{M}$ such that maximum absolute entry of $\widetilde{...

**3**

votes

**2**answers

193 views

### efficiently checking that a field extension is Galois

Let $K \subset L$ be an algebraic extension of fields finitely presented over a prime field or over an algebraically closed field. Is there an efficient procedure to check that $L/K$ is Galois? To ...

**0**

votes

**1**answer

153 views

### Refutation of $A \land \lnot\lnot\lnot A$ by resolution [closed]

$ A \land \lnot\lnot\lnot A $ this is a very simple example. Resolution is refutation complete. So it should be able to refute this formula. However, I don't see how would it do that without using ...

**3**

votes

**0**answers

72 views

### Weak randomness relative to finite-state machines

Is there a nice example of a sequence that looks random to any predictor whose predictions use a finite-state machine?
More precisely, consider a finite-state machine $M$ with input alphabet {0,1} ...

**4**

votes

**5**answers

303 views

### procedure-based (as opposed to definition-based) concepts

Euler's work on divergent series was guided by computational procedures, rather than any definition of the "value" of such a series. E.g., he was happy to have half a dozen procedures that indicated ...

**0**

votes

**3**answers

397 views

### System of quadratic equations with 18 unknown

So I want to solve for a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r which satisfy the following system of equations: ( I only need positive integer (or 0) solution)
a g + c h + b i + g j + i ...

**49**

votes

**14**answers

3k views

### Important open problems that have already been reduced to a finite but infeasible amount of computation

Most open problems, when formalized, naturally involve quantification over infinite sets, thereby obviating the possibility, even in principle, of "just putting it on a computer."
Some questions (e.g....

**16**

votes

**3**answers

1k views

### What to do when your research runs into a computationally challenging problem?

Occasionally, but more frequently lately, I would like to perform some hard computations. As an example, yesterday the following question came up:
What is the projective dimension of the edge ...

**3**

votes

**1**answer

471 views

### Efficiently computing with pullbacks and pushouts

Often when computing in category theory, one has to show that some square is cartesian. Depending on the number of maps involved, and their arrangement, it's somewhat difficult to write down exactly ...