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; Komolgorov Complexity and so on.

Filter by
Sorted by
Tagged with
25 votes
3 answers
3k 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 $...
Gil Kalai's user avatar
  • 24.2k
25 votes
1 answer
1k 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 $\sum_{n=0}^{\infty}f(n)=\...
Joseph Van Name's user avatar
24 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-...
Akhil Mathew's user avatar
  • 25.3k
24 votes
2 answers
2k views

Can one measure the infeasibility of four color proofs?

Terms like "impractical" and "unfeasible" are used to say the Robertson, Sanders, Seymour, and Thomas proof of the four color theorem needs computer assistance. Obviously no precise measure is ...
Colin McLarty's user avatar
24 votes
4 answers
4k 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 ...
Rune's user avatar
  • 2,386
24 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 ...
AlastairK's user avatar
  • 291
23 votes
2 answers
2k 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 ...
gowers's user avatar
  • 28.7k
22 votes
2 answers
6k views

$\mathbf{P} = \mathbf{NP}$, what's the problem?

Let's take the problem of the backpack: $A_1,\ldots ,A_n$ the weights that are integers, and we want to know if we can achieve a total weight of $V$. We take $$I=\dfrac{1}{2\pi}\int_0^{2\pi} \exp(-iVt)...
Dattier's user avatar
  • 3,737
22 votes
2 answers
2k 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 ...
Joseph O'Rourke's user avatar
22 votes
0 answers
1k views

Do we know how to determine the $2^{2020}$ decimal of $\sqrt{2}$?

In the case of $\dfrac{1}{7^{800}}$ it's easy, to find the $2^{2020}$ decimal, but what about the simplest of the irrational numbers. Question: Do we know how to determine the $2^{2020}$ decimal of $\...
Dattier's user avatar
  • 3,737
21 votes
5 answers
5k 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 ...
Ross Tang's user avatar
  • 571
21 votes
3 answers
6k views

What are the current breakthroughs of Geometric Complexity Theory?

I've read from Wikipedia about Geometric Complexity Theory (GCT) which (if I understood correctly) is a program for coping with the $ P=NP $ problem using algebraic methods. That program seems ...
21 votes
3 answers
6k 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 ...
Ryan Williams's user avatar
21 votes
2 answers
1k 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 ...
Scott Aaronson's user avatar
21 votes
0 answers
425 views

Straight-line drawing of regular polyhedra

Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane). For example, ...
Lviv Scottish Book's user avatar
20 votes
2 answers
2k views

Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$

As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis. Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...
20 votes
2 answers
2k 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 ...
Joseph O'Rourke's user avatar
20 votes
2 answers
17k views

Complexity of linear solvers vs matrix inversion

Solving linear equations can be reduced to a matrix-inversion problem, implying that the time complexity of the former problem is not greater than the time complexity of the latter. Conversely, given ...
Alm's user avatar
  • 1,159
20 votes
4 answers
838 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 ...
Gjergji Zaimi's user avatar
19 votes
12 answers
4k views

Lower Bounds in Theoretical Computer Science

Besides the classical: you can't do comparison sort with faster than (n logn); what are other lower bounds we know of for algorithms? I can't seem to dig them up via google scholar, yet they must ...
19 votes
1 answer
3k 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 ...
Gil Kalai's user avatar
  • 24.2k
19 votes
1 answer
604 views

How hard is it to tell when a finite set tiles the integers?

Given a nonempty set $B$ of integers between 1 and $n$, we wish to determine whether or not $\mathbb{Z}$ can be tiled with translates of $B$ (that is, covered by disjoint translates of $B$). I know an ...
James Propp's user avatar
  • 19.4k
19 votes
3 answers
2k 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-...
Jernej's user avatar
  • 3,433
19 votes
0 answers
505 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 ...
H A Helfgott's user avatar
  • 19.3k
19 votes
0 answers
776 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 ...
Lee Mosher's user avatar
  • 15.3k
18 votes
7 answers
3k views

SAT and Arithmetic Geometry

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note ...
Vanessa's user avatar
  • 1,368
18 votes
5 answers
2k views

Equivalent forms of the P vs. NP problem

Many things in math can be formulated quite differently; see the list of statements equivalent to RH here, for example, with RH formulated as a bound on lcm of consecutive integers, as an integral ...
Michael's user avatar
  • 2,175
18 votes
2 answers
3k 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, ...
András Salamon's user avatar
18 votes
4 answers
2k views

Kolmogorov complexity of classical music

I have an impression that classical music pieces are more "structured" than white noise and more "complicated" than the soundtracks of the Billboard Hot 100 songs. So assuming we ...
muse's user avatar
  • 197
18 votes
1 answer
2k views

Forcing over set theory versus forcing over arithmetic

I've been trying to understand better some of the research on forcing over bounded arithmetic and its connections with lower bounds in complexity theory. For example, Takeuti and Yasumoto have some ...
Timothy Chow's user avatar
  • 78.1k
18 votes
1 answer
857 views

Lagrange four-squares theorem --- deterministic complexity

Lagrange's four-squares theorem states that every natural number can be represented as the sum of four integer squares. Rabin and Shallit gave a randomised algorithm that finds one of these solutions ...
ckamath's user avatar
  • 283
18 votes
2 answers
1k views

Explicit invariant of tensors nonvanishing on the diagonal

The group $SL_n \times SL_n \times SL_n$ acts naturally on the vector space $\mathbb C^n \otimes \mathbb C^n \otimes \mathbb C^n$ and has a rather large ring of polynomial invariants. The element $$\...
Will Sawin's user avatar
  • 135k
18 votes
2 answers
1k views

Can Schwartz-Zippel be formulated for commutative rings instead of fields?

The polynomials which occur in the Schwartz-Zippel lemma could be defined for any commutative ring, yet the lemma is restricted to fields. This makes it inapplicable for $(1+x^n)=1+x^n(\operatorname{...
Thomas Klimpel's user avatar
18 votes
1 answer
1k views

Why should algebraic geometers and representation theorists care about geometric complexity theory?

Geometric complexity theory has demonstrated that complexity theorists should care about algebraic geometry and representation theory, but, why should algebraic geometers and representation theorists ...
Trent's user avatar
  • 999
18 votes
4 answers
2k views

Complexity of equitable partitions

We are talking about undirected simple graphs and partitions of their vertex sets into disjoint non-empty cells. Such a partition is equitable if for any two vertices $v,w$ in the same cell, and any ...
Brendan McKay's user avatar
17 votes
5 answers
7k views

What techniques exist to show that a problem is not NP-complete?

The standard way to show that a problem is NP-complete is to show that another problem known to be NP-complete reduces to it. That much is clear. Given a problem in NP, what's known about how to ...
Qiaochu Yuan's user avatar
17 votes
4 answers
6k views

Why is fast matrix multiplication impractical?

I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication. I read some content saying fast matrix multiplications are impractical because of large ...
Jiawei Ren's user avatar
17 votes
4 answers
3k views

Languages beyond enumerable

A language is a set of finite-length strings from some finite alphabet $\Sigma$. It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings. ...
Joseph O'Rourke's user avatar
17 votes
1 answer
1k views

Is it possible to make an algorithm that could predict the likelihood that a program will halt?

Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
AuSeR's user avatar
  • 303
17 votes
2 answers
2k views

What is the largest tensor rank of $n \times n \times n$ tensor?

The tensor rank of a three dimensional array $M[i,j,k], i,j,k\in [1,\ldots,n]$ is the minimal number of vectors $x_i,y_i,z_i$, such that $M=\sum_{i=1}^d x_i\otimes y_i\otimes z_i$. From dimension ...
Klim Efremenko's user avatar
17 votes
1 answer
862 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} d\...
Ganesh's user avatar
  • 617
17 votes
1 answer
552 views

Complexity of a Fibonacci numbers discrete log variation

In my work I encountered the following FIBMOD PROBLEM: Given $k,m$ in binary, decide if there exists $n$ such that $\, F_n = k \,$ (mod $m$). Here $F_n$ is a Fibonacci number. This is a variation ...
Igor Pak's user avatar
  • 16.3k
17 votes
1 answer
947 views

Polynomial-time algorithm to compare numbers in Conway chained arrow notation

I am looking for a polynomial-time algorithm which, given a character string containing two numbers in Conway's chained arrow notation for large numbers, indicates whether the first number is less ...
khaaan's user avatar
  • 171
16 votes
4 answers
1k views

Determining if some permutation of a vector satisfies a system of linear equations

Let $A$ be a matrix and $x$ a fixed vector. How can we determine whether or not there exists a permutation matrix $P$ such that $APx=0$? Does this problem reduce to anything well-understood?
Jack M's user avatar
  • 633
16 votes
8 answers
2k views

Examples of ubiquitous objects that are hard to find?

I've been wrestling with a certain research problem for a few years now, and I wonder if it's an instance of a more general problem with other important instances. I'll first describe a general ...
16 votes
2 answers
1k views

Is factorial definable using a $\Delta_0$ formula?

The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula. Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)? If not, why?
Yoni Zohar's user avatar
16 votes
3 answers
1k views

Are there any known quantum algorithms that clearly fall outside a few narrow classes?

I'm trying to refresh myself on quantum algorithms and have been skimming Childs and van Dam's 2008 RMP paper among other things. From my preliminary surfing it looks like the known quantum algorithms ...
Steve Huntsman's user avatar
16 votes
4 answers
949 views

Representing mathematical statements as SAT instances

The following problem (call it THEOREMS) belongs to class NP. Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary. Output: "Yes" if ...
Bogdan's user avatar
  • 781
16 votes
2 answers
3k views

Optimizing the condition number

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns $...
Igor Rivin's user avatar
  • 95.6k
16 votes
3 answers
1k views

symmetric integer matrices

Suppose I have a symmetric positive definite matrix $M$ with integer entries. I want to decide whether $M = A A^t,$ with $A$ likewise integral. I assume that decision problem is NP-complete, as is the ...
Igor Rivin's user avatar
  • 95.6k

1
2
3 4 5
26