All Questions
1,809 questions
113
votes
11
answers
18k
views
On mathematical arguments against Quantum computing
Quantum computing is a very active and rapidly expanding field of research. Many companies and research institutes are spending a lot on this futuristic and potentially game-changing technology. Some ...
110
votes
10
answers
15k
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 ...
89
votes
28
answers
20k
views
Which popular games have been studied mathematically?
I'm planning out some research projects I could do with undergraduates, and it struck me that problems analyzing games might be appropriate. As an abstract homotopy theorist, I have no experience with ...
83
votes
7
answers
7k
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 ...
- 44.3k
68
votes
8
answers
43k
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 ...
- 699
66
votes
4
answers
11k
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,...
59
votes
10
answers
26k
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?
58
votes
2
answers
18k
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}$). ...
- 15.5k
54
votes
2
answers
8k
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
August Ferdinand Möbius (November 17, 1790 – ...
54
votes
10
answers
8k
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-...
- 9,823
47
votes
7
answers
5k
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 ...
- 236k
47
votes
3
answers
12k
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 ...
- 20.2k
46
votes
8
answers
5k
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 ...
- 12.7k
46
votes
7
answers
13k
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 ...
- 6,694
44
votes
4
answers
5k
views
Why is "P vs. NP" necessarily relevant?
I want to start out by giving two examples:
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 planar $...
- 25.5k
44
votes
4
answers
2k
views
A curious process with positive integers
Let $k > 1$ be an integer, and $A$ be a multiset initially containing all positive integers. We perform the following operation repeatedly: extract the $k$ smallest elements of $A$ and add their ...
- 5,590
43
votes
10
answers
7k
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 ...
- 23k
35
votes
4
answers
5k
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$ ...
- 9,823
35
votes
8
answers
4k
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 ...
- 3,267
35
votes
4
answers
5k
views
Why are optimization problems often called "programs"?
Why are optimization problems often called programs?
linear programming
geometric programming
convex programming
Integer programming
...
- 461
35
votes
5
answers
4k
views
What are the strongest arguments for a genuine quantum computing advantage?
Despite having become a fairly mature field with enormous sums of money dumped into research and development, there does not as yet exist a formal proof that quantum computation actually provides an ...
- 766
35
votes
1
answer
2k
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 ...
- 2,993
33
votes
19
answers
6k
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 ...
- 1,088
33
votes
1
answer
1k
views
Is this conjecture strictly weaker than P=NP?
My three computability questions are related to the following group theory question (first asked by Bridson in 1996):
For which real $\alpha\ge 2$ the function $n^\alpha$ is equivalent to the Dehn ...
user6976
32
votes
2
answers
2k
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 ...
user6976
31
votes
4
answers
3k
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 ...
- 42.9k
31
votes
3
answers
3k
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$, ...
- 236k
30
votes
5
answers
14k
views
Can all convex optimization problems be solved in polynomial time using interior-point algorithms?
Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
- 303
30
votes
4
answers
2k
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 ...
- 493
30
votes
1
answer
2k
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 ...
- 4,529
30
votes
1
answer
7k
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 ...
- 381
30
votes
1
answer
592
views
Guess that group via product queries
Suppose someone (person B) knows a finite group $G$ of order $n$.
You (person A) know only the order $n$,
and that $1$ is the name of the identity element.
The group elements are named $1,2,\ldots,n$ ...
- 151k
30
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 ...
- 1,164
29
votes
7
answers
8k
views
Solving NP problems in (usually) Polynomial time?
Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
- 2,383
29
votes
3
answers
3k
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 ...
29
votes
2
answers
1k
views
Determining if a rational function has a subtraction-free expression
This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class.
Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
- 2,743
29
votes
6
answers
8k
views
How to find a closest integer point to the intersection of two lines?
Here's a question that originates from StackOverflow.
Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
- 391
29
votes
2
answers
1k
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 ...
- 29k
28
votes
5
answers
4k
views
Are there any computational problems in groups that are harder than P?
There are several well known classes of groups for which the word problem, conjugacy etc. are solvable in polynomial time (hyperbolic, automatic).
Then there are several classes of groups like ...
- 391
28
votes
2
answers
3k
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 ...
- 47.3k
28
votes
2
answers
2k
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 ...
- 5,502
28
votes
4
answers
5k
views
Complexity of testing integer square-freeness
How fast can an algorithm tell if an integer is square-free?
I am interested in both deterministic and randomized algorithms. I also care about both unconditional results and ones conditional on GRH ...
- 4,994
27
votes
5
answers
2k
views
Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?
Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows:
$$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$
For example, if $m=3$, the matrix is
$$\begin{pmatrix}6 & 20 & 6& 0 ...
- 1,121
27
votes
10
answers
4k
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$ ...
- 711
27
votes
4
answers
8k
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 ...
- 503
27
votes
3
answers
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, ...
- 595
27
votes
0
answers
1k
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 ...
- 666
26
votes
4
answers
7k
views
What would be some major consequences of the inconsistency of ZFC?
Update (21st April, 2019). Removed the reference / initial trigger behind my question (please see comment thread below for the reasons). Am retaining, of course, the actual question, noted both in the ...
- 28.6k
26
votes
6
answers
9k
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 ...
- 1,593
26
votes
6
answers
7k
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 ...
- 29k