**74**

votes

**9**answers

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

**49**

votes

**9**answers

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

**46**

votes

**5**answers

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

**41**

votes

**2**answers

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

**38**

votes

**3**answers

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

**34**

votes

**6**answers

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

**33**

votes

**7**answers

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

**33**

votes

**2**answers

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

**32**

votes

**9**answers

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

**30**

votes

**7**answers

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

**30**

votes

**4**answers

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

**29**

votes

**4**answers

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

**29**

votes

**1**answer

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

**29**

votes

**1**answer

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

**28**

votes

**2**answers

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

**26**

votes

**19**answers

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

**26**

votes

**7**answers

6k 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?

**26**

votes

**10**answers

2k 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$ ...

**26**

votes

**8**answers

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

**25**

votes

**1**answer

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

**25**

votes

**3**answers

1k 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, ...

**25**

votes

**1**answer

759 views

### Are sums of sequences decidable?

Suppose that $f,g$ are rational functions with integer coefficients such that $\sum_{n=0}^{\infty}f(n)$ and $\sum_{n=0}^{\infty}g(n)$ both converge. Is it decidable whether
...

**24**

votes

**6**answers

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

**24**

votes

**4**answers

2k views

### Algebraic P vs. NP

I recently attended a lecture where the speaker mentioned that what he was talking about was connected to the algebraic version of the $P$ vs. $NP$ problem. Could someone explain what that means in a ...

**24**

votes

**0**answers

596 views

### A combination of two well-known complexity problems

Suppose you are given two graphs $G$ and $H$ and are told that one of the following two situations occurs. Either they are isomorphic, or one of the graphs contains a Hamilton cycle and the other ...

**23**

votes

**2**answers

1k views

### Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?

Question. Given a Turing-machine program $e$, which
is guaranteed to run in polynomial time, can we computably
find such a polynomial?
In other words, is there a
computable function $e\mapsto p_e$, ...

**23**

votes

**1**answer

3k views

### Why is proving P != NP so hard?

Does anyone have any insight into why it is so hard to prove that P != NP conjecture? There seems to be so much evidence in its favor, and so many problems and techniques with which to attack it, that ...

**23**

votes

**2**answers

3k views

### Counting subgraphs of bipartite graphs

I'm not a graph theorist or computational complexity specialist, so my apologies if this question is stupid or poorly posed!
Given a bipartite graph $G$ of $n$ vertices, how many induced subgraphs of ...

**22**

votes

**4**answers

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

**22**

votes

**6**answers

4k views

### Are there any interesting examples of random NP-complete problems?

Here's an example of the kind of thing I mean. Let's consider a random instance of 3-SAT, where you choose enough clauses for the formula to be almost certainly unsatisfiable, but not too many more ...

**21**

votes

**3**answers

2k views

### Discrete Fourier Transform of the Möbius Function

Consider the Möbius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Next consider for some natural number ...

**20**

votes

**5**answers

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

**20**

votes

**3**answers

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

**20**

votes

**2**answers

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

**20**

votes

**2**answers

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

**20**

votes

**2**answers

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

**19**

votes

**1**answer

4k views

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

Background: The Strassen Algorithm, described here, has a computational complexity of $\text{O}(n^{2.8})$ for the multiplication of two $n \times n$ matrices. However, the constant is so large that ...

**19**

votes

**4**answers

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

**18**

votes

**2**answers

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

**18**

votes

**3**answers

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

**18**

votes

**0**answers

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

**18**

votes

**0**answers

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

**17**

votes

**5**answers

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

**17**

votes

**1**answer

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

**17**

votes

**4**answers

675 views

### Enumeration and random selection

In Peter J. Cameron's book "Permutation Groups" I found the following quote
It is a slogan of modern enumeration theory that the ability to count a set is closely related to the ability to pick a ...

**17**

votes

**1**answer

593 views

### An NP-hard $n$ fold integral

We are given rational numbers $[c_1, c_2, \ldots, c_n]$ and $v$ from the interval $[0,1]$.
Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} ...

**16**

votes

**5**answers

1k views

### Are there complexity classes with provably no complete problems?

A problem is said to be complete for a complexity class $\mathcal{C}$ if a) it is in $\mathcal{C}$ and b) every problem in $\mathcal{C}$ is log-space reducible to it. There are natural examples of ...

**16**

votes

**2**answers

1k views

### “a shape that … lies halfway between a square and a circle”

An article in the
Notices of the AMS, Volume 61, Issue 10, 2014
(PDF download link),
on Khot's Unique Games Conjecture, says this:
Another group ... found a
shape that in a certain sense lies ...

**16**

votes

**2**answers

2k views

### Is #k-XORSAT #P-complete?

k-XORSAT is the problem of deciding whether a Boolean formula $$\bigwedge_{i \in I} \oplus_{j=1}^k l_{s_{ij}}$$ is satisfiable. Here $\oplus$ denotes the binary XOR operation, $I$ is some index set, ...

**16**

votes

**2**answers

465 views

### Minimum number of variables on which a multivariate polynomial depends?

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