# Tagged Questions

computational complexity theory; complexity classes, such as P, NP, PSPACE, and so on; resource-limited computation; NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models such as automata, circuits; regular languages; ...

9k views

### Analogues of P vs. NP in the history of mathematics

Recently I wrote a blog post entitled "The Scientific Case for P≠NP". The argument I tried to articulate there is that there seems to be an "invisible electric fence" separating the problems in P ...
4k views

### What are the implications of the new quasi-polynomial time solution for the Graph Isomorphism problem?

This week, news came out that Laszlo Babai has found a quasi-polynomial time algorithm to solve the Graph Isomorphism problem (that is: $O(\exp(polylog(n)))$). He is giving a series of talks this week,...
3k views

### Computational complexity of computing homotopy groups of spheres

At various times I've heard the statement that computing the group structure of $\pi_k S^n$ is algorithmic. But I've never come across a reference claiming this. Is there a precise algorithm ...
6k views

### The “sensitivity” of 2-colorings of the d-dimensional integer lattice

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate). Let $C$ be a two-...
6k views

### Walsh Fourier Transform of the Möbius function

This question is related to this previous question where I asked about ordinary Fourier coefficients. Special case: is Möbius nearly Orthogonal to Morse ! Harold Calvin Marston Morse (24 March ...
8k views

### Testing whether an integer is the sum of two squares

Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer $n$ is a sum of two squares? By "fast" here I mean polynomial time (i.e. time $O((log n)^{O(1)})$). Note ...
3k views

### Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
4k views

### What is the time complexity of computing sin(x) to t bits of precision?

Short version of the question: Presumably, it's poly$(t)$. But what polynomial, and could you provide a reference? Long version of the question: I'm sort of surprised to be asking this, because ...
19k views

### Example of a good Zero Knowledge Proof.

I am working on my zero knowledge proofs and I am looking for a good example of a real world proof of this type. An even better answer would be a Zero Knowledge Proof that shows the statement isn't ...
4k views

### What is the easiest randomized algorithm to motivate to the layperson?

When trying to explain complexity theory to laypeople, I often mention randomized algorithms but seemingly lack good examples to motivate their usage. I often want to mention primality testing but ...
4k views

### What is the shortest program for which halting is unknown?

In short, my question is: What is the shortest computer program for which it is not known whether or not the program halts? Of course, this depends on the description language; I also have the ...
2k views

### Why is “P vs. NP” necessarily relevant?

I want to start out by giving two examples: 1) Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a ...
1k views

### How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
3k views

### An edge partitioning problem on cubic graphs

Hello everyone, I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...
3k views

### Can a problem be simultaneously polynomial time and undecidable?

The Robertson-Seymour theorem on graph minors leads to some interesting conundrums. The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...
3k views

### Massive cancellations

Let $A=\{a_1,\ldots,a_k\}$ be a fixed, finite set of reals. Let $S_A(n)$ be the set of all reals that are expressible as the sum of at most $2^n$ terms, where each term is a product of at most $n$ ...
8k views

### Problems known to be in both NP and coNP, but not known to be in P

One such problem I know is integer factorization. What are other interesting cases?
1k views

### The NP version of Matiyasevich's theorem

By Matiyasevich, for every recursively enumerable set $A$ of natural numbers there exists a polynomial $f(x_1,...,x_n)$ with integer coefficients such that for every $p\ge 0$, $f(x_1,...,x_n)=p$ has ...
2k views

### Is P=NP relevant to finding proofs of everyday mathematical propositions?

Disclaimer: I don't know a whole lot about complexity theory beyond, say, a good undergrad class. With increasing frequency I seem to be encountering claims by complexity theorists that, in the ...
6k views

### How fast can we *really* multiply matrices?

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.807})$ for the multiplication of two $n \times n$ matrices (the exponent is $\frac{\log7}{\log2}$). ...
3k views

### Can We Decide Whether Small Computer Programs Halt?

The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not. Are there some large $n$ ...
1k views

### A programming language that can only create algorithms with polynomial runtime?

Has someone constructed a programming language that can construct all the algorithms in P, and no others? I'm interested in this restriction coming from the syntax naturally, as opposed to just being ...
941 views

### How strong is this conjecture? $(Z/nZ)^*$ is generated by “small” elements

Conjecture: There are constants $c,k$ such that every $(Z/nZ)^*$ is generated by its elements smaller than $k (\log n)^c$. Where $(Z/nZ)^*$ is the multiplicative group of integers mod $n$. My main ...
2k views

### Why do statistical randomness tests seem so ad hoc?

Wikipedia describes Kendall and Smith's 1938 statistical randomness tests like this: The frequency test, was very basic: checking to make sure that there were roughly the same number of 0s, 1s, ...
778 views

1k views

### What is the complexity of this problem?

Recently on Dick Lipton and Ken Regan's blog there was a post about problems of intermediate complexity, that is, NP problems that are harder than P but easier than NP-complete. The main message of ...
3k views

### Why relativization can't solve NP !=P?

If this problem is really stupid, please close it. But I really wanna get some answer for it. And I learnt computational complexity by reading books only. When I learnt to the topic of relativization ...
2k views

### Is the theory of categories decidable?

There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led me to consider the ...
970 views

### Deep theorems and long proofs

I ran across this discussion by Daniel Shanks, "Is the quadratic reciprocity law a deep theorem?." Solved and Unsolved Problems in Number Theory. Vol. 297. AMS, 2001. p.64ff. which made me ...
2k views

### Simulating Turing machines with {O,P}DEs.

Qiaochu Yuan in his answer to this question recalls a blog post (specifically, comment 16 therein) by Terry Tao: For instance, one cannot hope to find an algorithm to determine the existence of ...
1k views

### Is there a syntactic characterization for BPP, BQP, or QMA?

Background The complexity classes BPP, BQP, and QMA are defined semantically. Let me try to explain a little bit what is the difference between a semantic definition and a syntactic one. The ...
2k views

### How do we know that P != LINSPACE without knowing if one is a subset of the other?

I've seen that P != LINSPACE (by which I mean SPACE(n)), but that we don't know if one is a subset of the other. I assume that means that the proof must not involve showing a problem that's in one ...
2k views

### Discrete logs vs. factoring

One thing that I've never quite understood is why computing discrete logarithms (in the multiplicative group mod p) and factoring seem to be so closely related. I don't think that there's a reduction ...
1k views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in sub-...
693 views

### Computational complexity of topological K-theory

I am a novice with K-theory trying to understand what is and what is not possible. Given a finite simplicial complex $X$, there of course elementary ways to quickly compute the cohomology of $X$ with ...
3k views

### Satisfiability of general Boolean formulas with at most two occurrences per variable

(If you know basics in theoretical computer science, you may skip immediately to the dark box below. I thought I would try to explain my question very carefully, to maximize the number of people that ...
375 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 ...
564 views

### Reference request: Parallel processor theorem of William Thurston

Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...
2k views

### Super-linear time complexity lower bounds for any natural problem in NP?

Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd ...
5k views

### The problem of finding the first digit in Graham's number

Motivation In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could ...
2k views

### Möbius Randomness of the Rudin-Shapiro Sequence

The Rudin-Shapiro sequence (also known as the Golay-Rudin-Shapiro sequence) is defined as follows. Let $a_n = \sum \epsilon_i\epsilon_{i+1}$ where $\epsilon_1,\epsilon_2,\dots$ are the digits in the ...
Let $p:F_2^n\rightarrow F_2$ be a multivariate polynomial, let's say of degree 3. (Both the degree and the order of the field could probably be replaced by other constants without affecting this ...