Questions tagged [computational-complexity]
This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Kolmogorov Complexity and so on.
1,369 questions
119 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 ...
114 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 ...
93 votes
28 answers
21k 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 ...
84 votes
7 answers
8k 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 ...
- 45.3k
68 votes
8 answers
45k 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
12k 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,...
63 votes
11 answers
27k 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?
59 votes
2 answers
20k 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.9k
55 votes
10 answers
9k 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,893
54 votes
2 answers
9k 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 – ...
48 votes
11 answers
8k 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 ...
- 23.7k
47 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 ...
- 13.7k
47 votes
7 answers
6k 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 ...
- 246k
47 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,764
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 ...
- 21.7k
46 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 $...
- 26.2k
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,752
36 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 ...
- 3,035
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,893
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,297
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 ...
- 1,010
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
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 ...
- 43.5k
32 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$, ...
- 246k
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
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,929
30 votes
7 answers
9k 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,463
30 votes
5 answers
15k 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
3 answers
4k 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 ...
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
8k 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 ...
- 401
30 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 ...
- 5,264
30 votes
1 answer
660 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$ ...
- 153k
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
5 answers
5k 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 ...
- 401
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,783
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 ...
- 29.4k
28 votes
4 answers
8k 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.7k
28 votes
4 answers
9k 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 ...
- 513
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 ...
- 48.2k
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,692
28 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 ...
- 676
27 votes
10 answers
5k 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$ ...
- 731
27 votes
4 answers
6k 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 ...
- 12.8k
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, ...
- 615
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 ...
- 29.4k
25 votes
5 answers
3k 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 NP-...
- 26.2k
25 votes
1 answer
6k views
Evidence for integer factorization is in $P$
Peter Sarnak believes that integer factorization is in $P$. It is a well-known open problem in TCS to identify the real complexity class of integer factorization. Take a look at this link for Peter ...
- 810
25 votes
2 answers
2k views
Who first dubbed them "expander graphs"?
Expander graphs ("sparse graphs that have strong connectivity properties") burst onto the mathematical scene around the millennium, but I have not been successful in tracing the origin of (a) the ...
- 153k