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.
1,297
questions
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 $...
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)=\...
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-...
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 ...
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 ...
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 ...
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 ...
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)...
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 ...
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 $\...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 $$\...
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{...
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 ...
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 ...
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 ...
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 ...
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.
...
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 ...
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 ...
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\...
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 ...
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 ...
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?
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?
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 ...
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 ...
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 $...
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 ...